AtCoder Beginner Contest 219

https://atcoder.jp/contests/abc219

F - Cleaning Robot

题意

在一张网格图中，给定一个指令序列。问重复 $k$ 次一共能访问到多少个不同的点。

数据范围：$1\leq |s|\leq 2\times10^5,1\leq k\leq 10^{12}$。

题解

先模拟一遍序列，得到 $|s|$ 个点。那么记执行一次序列移动量为 $(dx,dy)$。那么就相当于是每个点走了 $k$ 次 $(dx,dy)$。只需要考虑重复的情况，将处于相同直线上的点且下标模 $a$ 相同的点放在一起即可。

G - Propagation

题意

给定一张 $n$ 个点 $m$ 条边的无向图。第 $i$ 个点初始点权为 $i$。有 $q$ 次询问，每次询问 $x$，将与 $x$ 相邻的所有点点权修改为 $x$ 的点权。要求最终输出每个点的点权。

数据范围：$n,m,q\leq 2\times10^5$。

题解

考虑根号分治，称度数大于 $\sqrt{n}$ 的点为关键点。对于每个点维护点权和修改时间。每次修改时，如果是非关键点，则暴力修改，如果是关键点，则记录下这次推送的点权和时间。每次查询时，查询自身的点权和相邻所有关键点的推送点权，取时间最靠近的即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+5;
pii a[N],b[N];
vector<int> g[N],g0[N];
bool flag[N];
void query(int x)
{
    pii tmp=a[x];
    for(auto i:g0[x])
        if(b[i].second>tmp.second) tmp=b[i];
    a[x]=tmp;
}
void update(int x,int y)
{
    if(flag[x]) b[x]={a[x].first,y};
    else
    {
        for(auto i:g[x]) a[i]={a[x].first,y};
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;cin>>n>>m>>q;
    int b=sqrt(n);
    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++) 
    {
        a[i]={i,0};
        if((int)g[i].size()>=b) flag[i]=1;
    }
    for(int i=1;i<=n;i++)
        for(auto v:g[i])
            if(flag[v]) g0[i].push_back(v);
    for(int i=1;i<=q;i++)
    {
        int x;cin>>x;
        query(x);
        update(x,i);
    }
    for(int i=1;i<=n;i++) 
    {
        query(i);
        cout<<a[i].first<<" \n"[i==n];
    }
    return 0;
}