[BOJ] 14267 회사 문화1 c++

문제 링크

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

핵심 알고리즘

직속 상사의 번호를 p배열에 저장한다.

m번 동안 score 배열에 칭찬의 수치를 저장한다. 이때, 칭찬의 수치를 입력받을때마다 직속 부하에게 저장하면 시간초과가 난다.

m번 반복이 끝나면 직속 부하에게 내리 칭찬을 해준다. 칭찬의 정도는 직속 상사의 score만큼 더한다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> adj[100001];
int score[100001];
int p[100001];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        if (p[i] != -1)
            adj[p[i]].push_back(i);
    }

    while (m--) {
        int i, w;
        cin >> i >> w;
        score[i] += w;
    }

    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        score[cur] += score[p[cur]];
        for (auto nxt : adj[cur])
            q.push(nxt);
    }

    for (int i = 1; i <= n; i++)
        cout << score[i] << " ";
    
}