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

 

• 상사가 칭찬을 받으면, 부하들도 같은 수치 만큼 똑같이 칭찬을 받는다.
• 부하와 사장 간의 연결 관계를 저장하는 배열을 설정 adj(여러 명 가질 수도 있으니까 vector로 선언)
  • 처음에는 칭찬 받을 때마다 BFS로 탐색하면서 갱신하게 코드를 구현
  • 그랬더니 시간 초과가 발생, 생각해보면 최악의 경우 약 n x m (최대 10^10) 연산이 일어날 수 있어 2초에 처리가 불가

레전드 시간 초과 발생~

• 그렇다면 어떻게? 그냥 따로 배열을 하나 더 추가해서 "한 번에 누적에서 처리하는 방식"으로 변경

cum[child] = cum[parent] + praise[child] (이런 느낌으로?)

 

-> 성공

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> adj[100001];
vector<int> praise(100001, 0);
vector<int> result(100001, 0);

int main() {
    cin >> n >> m;

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


    for (int j = 1; j <= m; j++) {
        int i, w; cin >> i >> w;
        praise[i] += w;
    }

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

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

        for (int nxt: adj[cur]) {
            result[nxt] = result[cur] + praise[nxt];
            q.push(nxt);
        }
    }

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

    return 0;
}

 

링크

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