[AGC012B] Splatter Painting

Link

考虑倒着做，则一次被染色后就不会被二次染色。

考虑染色时记录最大半径，若小于该值就不染色。

显然，每个点最多经过 \(d+1\) 次，复杂度 \(\mathcal O(nd)\)

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
    x=0;int w=0;char c=GetC();
    for(;!isdigit(c);w|=c=='-',c=GetC());
    for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
    if(w) x=-x;
    return in;
}
const int N=1e5+5;
struct EDGE{int nxt,to;}e[N<<1];
int head[N],tot;
void add(int from,int to){
    e[++tot].nxt=head[from];
    e[tot].to=to;
    head[from]=tot;
}
struct query_t{int u,d,c;}Q[N];
int mxd[N];
int col[N];
void dfs(int u,int d,int c){
    if(mxd[u]>=d) return ;
    mxd[u]=d;
    if(col[u]==-1) col[u]=c;
    for(int i=head[u];i;i=e[i].nxt){
        dfs(e[i].to,d-1,c);
    }
}
int main(){
    int n,m;io>>n>>m;
    for(int i=1;i<=n;++i) mxd[i]=col[i]=-1;
    for(int i=1;i<=m;++i){
        int u,v;io>>u>>v;
        add(u,v);add(v,u);
    }
    int q;io>>q;
    for(int i=1;i<=q;++i) io>>Q[i].u>>Q[i].d>>Q[i].c;
    for(int i=q;i;--i){
        dfs(Q[i].u,Q[i].d,Q[i].c);
    }
    for(int i=1;i<=n;++i) printf("%d\n",col[i]==-1?0:col[i]);
    return 0;
}

原文地址：http://www.cnblogs.com/pref-ctrl27/p/16860967.html