Submission #1520499


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int dmax;
vector<vector<int>> G;
vector<vector<int>> color;

void bfs(int s, int d, int c) {
  queue<P> que;
  que.push({s, d});
  while (!que.empty()) {
    P p = que.front(); que.pop();
    int u = p.first, l = p.second;
    if (color[u][l] >= 0) continue;
    for (int i = 0; i <= l; i++) {
      if (color[u][i] == -1) color[u][i] = c;
    }
    for (auto&& v : G[u]) que.push({v, l - 1});
  }
}
main() {
  int N, M; cin >> N >> M;
  G.resize(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int Q; cin >> Q;
  vector<int> v(Q), d(Q), c(Q);
  for (int i = 0; i < Q; i++) {
    cin >> v[i] >> d[i] >> c[i];
    v[i]--;
    dmax = max(dmax, d[i]);
  }
  color.assign(N, vector<int>(dmax + 1, -1));
  for (int i = Q - 1; i >= 0; i--) {
    bfs(v[i], d[i], c[i]);
  }
  for (int i = 0; i < N; i++) cout << ( (color[i][0] == -1) ? 0 : color[i][0] ) << endl;
}

Submission Info

Submission Time
Task B - Splatter Painting
User hrbt
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1062 Byte
Status AC
Exec Time 368 ms
Memory 16760 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 2
AC × 19
AC × 35
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt
All 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
10_01.txt AC 2 ms 256 KB
10_02.txt AC 1 ms 256 KB
10_03.txt AC 1 ms 256 KB
10_04.txt AC 1 ms 256 KB
10_05.txt AC 2 ms 256 KB
10_06.txt AC 1 ms 256 KB
10_07.txt AC 4 ms 384 KB
10_08.txt AC 8 ms 512 KB
10_09.txt AC 7 ms 512 KB
10_10.txt AC 8 ms 512 KB
10_11.txt AC 8 ms 512 KB
10_12.txt AC 7 ms 512 KB
10_13.txt AC 6 ms 512 KB
10_14.txt AC 5 ms 512 KB
10_15.txt AC 5 ms 512 KB
10_16.txt AC 7 ms 640 KB
10_17.txt AC 7 ms 512 KB
20_01.txt AC 366 ms 15616 KB
20_02.txt AC 359 ms 15616 KB
20_03.txt AC 368 ms 15616 KB
20_04.txt AC 40 ms 2060 KB
20_05.txt AC 7 ms 384 KB
20_06.txt AC 155 ms 11008 KB
20_07.txt AC 8 ms 384 KB
20_08.txt AC 63 ms 1280 KB
20_09.txt AC 7 ms 384 KB
20_10.txt AC 64 ms 1152 KB
20_11.txt AC 83 ms 1664 KB
20_12.txt AC 229 ms 13440 KB
20_13.txt AC 310 ms 14848 KB
20_14.txt AC 322 ms 14592 KB
20_15.txt AC 334 ms 16760 KB
20_16.txt AC 343 ms 16760 KB