Submission #1833072

---

Source Code Expand

#include<bits/stdc++.h>
#define out(x) cerr << #x << " = " << x << "\n"
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
  x = 0;char c = getchar();bool f = 0;
  for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
  for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if(f) x = -x;
}

static const int N = 520233, M = 5202333;
struct E {
  int nxt, u, v, w;
}e[M];
int head[N], ct[N], book[N], dis[N];
int cnt = 0, n, m, Q;
int nQ;
int sccno[N], Max[N];
inline void add(int u, int v, int w = 0) {
  e[++ cnt] = (E) {head[u], u, v, w}; head[u] = cnt;
}

inline void dfs(int u, int d, int col) {
  if(d == -1) return ; 
//  cout << u << "\n";
  if(Max[u] < d) {
    if(!sccno[u]) sccno[u] = col;
    Max[u] = d;
    for(int i = head[u]; i; i = e[i].nxt) {
      int v = e[i].v;
      dfs(v, d - 1, col);
    }
  }
}

struct Query {
  int u, d, c;
}q[N];

int main() {
  read(n); read(m);
    fill(Max, Max + n + 1, -2333);
  for(int i = 1; i <= m; i ++) {
    int u, v, w; read(u); read(v);
    add(u, v);
    add(v, u);
     }
  read(Q);
  for(int i = 1; i <= Q; i ++) {
    int u, d, c;
    read(u); read(d); read(c);
     q[i] = (Query) {u, d, c};
  }
  for(int i = Q; i >= 1; i --) {
    Query &u = q[i];
//    cout << u.u << ' ' << u.d << " " << u.c << "\n";
    dfs(u.u, u.d, u.c);
//    for(int i = 1; i <= n; i ++) cout << Max[i] << "\t";
//    putchar('\n');
  }
  for(int i = 1; i <= n; i ++) cout << sccno[i] << "\n";
}

Submission Info

Judge Result