Submission #1196806


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define ALL(a) begin(a), end(a)
#define SZ(a) ((int)(a).size())

#ifdef __DEBUG
#define debug if (true)
#else
#define debug if (false)
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define fixed asldkjasld

const int N = 1e5 + 5;

int n, m, q;
int c[N];
bool fixed[N];
vector<pii> g[N];
vi maxDist[N];
tuple<int, int, int> qs[N];
map<int, int> pos[N];

void dfs(int u, int rem, int from, int newC) {
  if (maxDist[u][from] >= rem) {
    return;
  }
  maxDist[u][from] = rem;
  if (!fixed[u]) {
    fixed[u] = true;
    c[u] = newC;
  }
  if (rem <= 0) {
    return;
  }
  for (auto &it : g[u]) {
    int v = it.first, w = it.second;
    dfs(v, rem - 1, w, newC);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    g[u].push_back(pii(v, -1));
    g[v].push_back(pii(u, -1));
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < SZ(g[i]); j++) {
      int to = g[i][j].first;
      pos[i][to] = j;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < SZ(g[i]); j++) {
      int to = g[i][j].first;
      g[i][j].second = pos[to][i];
    }
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v, d, c;
    cin >> v >> d >> c;
    v--;
    qs[i] = make_tuple(v, d, c);
  }
  for (int i = 0; i < n; i++) {
    maxDist[i].assign(SZ(g[i]) + 1, -1);
  }
  for (int i = q - 1; i >= 0; i--) {
    int start, maxDist, newC;
    tie(start, maxDist, newC) = qs[i];
    dfs(start, maxDist, SZ(g[start]), newC);
  }
  for (int i = 0; i < n; i++) {
    printf("%d\n", c[i]);
  }
  return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User raisfathin
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1795 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
Subtask1 200 / 200 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 0 / 500 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 5 ms 10880 KB
00_example_02.txt 5 ms 10880 KB
10_01.txt 6 ms 11008 KB
10_02.txt 5 ms 10880 KB
10_03.txt 5 ms 10880 KB
10_04.txt 5 ms 10880 KB
10_05.txt 6 ms 11008 KB
10_06.txt 5 ms 10880 KB
10_07.txt 5 ms 10880 KB
10_08.txt 7 ms 11136 KB
10_09.txt 7 ms 11136 KB
10_10.txt 7 ms 11136 KB
10_11.txt 7 ms 11136 KB
10_12.txt 7 ms 11136 KB
10_13.txt 6 ms 11136 KB
10_14.txt 6 ms 11136 KB
10_15.txt 6 ms 11136 KB
10_16.txt 74 ms 11136 KB
10_17.txt 74 ms 11136 KB
20_01.txt 151 ms 27648 KB
20_02.txt 152 ms 27648 KB
20_03.txt 147 ms 27648 KB
20_04.txt 64 ms 16000 KB
20_05.txt 6 ms 10880 KB
20_06.txt 18 ms 14464 KB
20_07.txt 6 ms 10880 KB
20_08.txt 40 ms 11904 KB
20_09.txt 7 ms 10880 KB
20_10.txt 21 ms 10880 KB
20_11.txt 37 ms 11776 KB
20_12.txt 82 ms 26240 KB
20_13.txt 114 ms 26880 KB
20_14.txt 118 ms 26368 KB
20_15.txt
20_16.txt