Submission #19182561

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=1e5;
int n,m,ask_n,col[N],f[N],ask[N][3];

//Graph
vector<int> adj[N];
void adde(int u,int v)
    {adj[u].pb(v),adj[v].pb(u);}

//Main
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    R(i,m){
        int u,v;
        cin>>u>>v,--u,--v;
        adde(u,v);
    }
    R(u,n) col[u]=f[u]=-1;
    cin>>ask_n;
    R(i,ask_n){
        R(t,3) cin>>ask[i][t];
        --ask[i][0],--ask[i][2];
    }
    L(i,ask_n){
        queue<int> q;
        int s=ask[i][0],d=ask[i][1],c=ask[i][2];
        if(f[s]>=d) continue;
        q.push(s),f[s]=ask[i][1];
        if(!~col[s]) col[s]=c;
        while(sz(q)){
            int u=q.front();
            q.pop();
            for(int v:adj[u])if(f[v]<f[u]-1){
                f[v]=f[u]-1,q.push(v);
                if(!~col[v]) col[v]=c;
            }
        }
    }
    R(u,n) cout<<col[u]+1<<'\n';
    return 0;
}

Submission Info

Judge Result