ABC138-D. Ki

작성일

https://atcoder.jp/contests/abc138/tasks/abc138_d

  • 고작 초기조건 하나때문에 40분을 잡아먹은 치욕적인 문제이다.
  • 문제 자체는 BFS하면 끝나는 문제로 간단한다.
  • ans 배열을 0으로 초기화해두는 바람에 WA를 4번이나 맞고 -_-..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
int N, Q, a, b;
vector<int> adj[MAXN+1];
int point[MAXN+1];
int ans[MAXN+1];

int main() {
  ios::sync_with_stdio(false);
  cin >> N >> Q;
  for(int i = 0; i < N-1; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i = 0; i < Q; i++) {
    cin >> a >> b;
    point[a] += b;
  }
  for(int i = 1; i <= N; i++)
    ans[i] = -1;

  queue<int> q;
  q.push(1);
  ans[1] = point[1];

  while(q.size()) {
    int cur = q.front(); q.pop();
    for(int x : adj[cur]) {
      if(ans[x] != -1) continue;
      ans[x] = ans[cur] + point[x];
      q.push(x);
    }
  }
  for(int i = 1; i <= N; i++)
    cout << ans[i] << " ";
}