[BOJ] 14267번 회사 문화 1 (C++)

https://www.acmicpc.net/problem/14267

14267번: 회사 문화 1

 

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;

int n, m;
vector<int> v[MAX];
int cpm[MAX];

void dfs(int num){
	for(int i = 0; i < v[num].size(); i++){
		cpm[v[num][i]] += cpm[num];
		dfs(v[num][i]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;

	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		if(x != -1){
			v[x].push_back(i);
		}
	}
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		cpm[a] += b;
	}
	
	dfs(1);
	
	for(int i = 1; i <= n; i++){
		cout << cpm[i] << " ";
	}
	return 0;
}

 

처음에 풀 땐 칭찬 수치를 저장하지 않고 칭찬을 입력받을 때마다 dfs를 돌려서 시간 초과가 났다.

칭찬 수치를 먼저 cpm[]에 저장하고, root 노드인 1번부터 dfs를 실행하여 수치를 누적해가며 더해주어야 한다.