[ABC219G] Propagation

ziyistudy · 2024-03-09 12:19:23 · 题解

学校断网 VP 的时候 A 的，于是决定来写一篇题解。

很容易就可以想到根号分治。至于为什么可以想到，引用某大佬的话“啪的一下就想到根号分治，很快啊”。

以下简称与节点 u 直接相连的节点的个数（即节点 u 的边数）为 u 的大小。令 hal=\sqrt{2\times10^5}。

当你发现：大小超过 hal 的节点不会超过 hal 个时，本题就结束了（证明过于简单，此处略）。

所以，当点 u 的大小小于 hal，直接暴力染色周围节点即可；否则，给当前节点打上标记（分别为：颜色和时间）。

当要更新该节点时，只需要搜索与它直接相连的节点中大小不超过 hal 的节点，依次查看是否需要更新（更新时查看该节点的更改时间是否晚于本节点）。

以上操作均为更号级别。

时间复杂度：O(q\sqrt{m})。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int hal=450;
vector<vector<int>> G(N);
vector<vector<int>> nxt(N);
int a[N];
int col[N],tim[N],tim1[N];
signed main()
{

    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n;i++) a[i]=i;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(G[i].size()<hal) continue;
        for(auto it:G[i]) nxt[it].push_back(i);
    }
    for(int i=1;i<=q;i++)
    {
        int dir;cin>>dir;

        int cnt=0,maxn=0;
        for(auto it:nxt[dir]) {
            if(tim1[it]>maxn&&tim1[it]>tim[dir]){
                maxn=tim1[it];
                cnt=col[it];
            }
        }
        if(cnt!=0) a[dir]=cnt,tim[dir]=maxn;

        if(G[dir].size()<hal) for(auto it:G[dir]) a[it]=a[dir],tim[it]=i;
        else {
            col[dir]=a[dir];
            tim1[dir]=i;
        }
    }
    for(int i=1;i<=n;i++) {
        int cnt=0,maxn=0;
        for(auto it:nxt[i]) {
            if(tim1[it]>maxn&&tim1[it]>tim[i]){
                maxn=tim1[it];
                cnt=col[it];
            }
        }
        if(cnt!=0) a[i]=cnt,tim[i]=maxn;
        cout<<a[i]<<" ";
    }
}