P4616 [COCI2017-2018#5] Pictionary

2018-11-06 14:25:45


题意: $n$ 个点,一开始没有边,第 $i$ 天在 $gcd(a,b)=m-i+1$ 的两点之间连边,共 $m$ 天。多组询问 $x,y$ 最早在第几天连通


发现第 $i$ 天只需从 $m-i+1$ 向它的倍数连边

这样两个以 $m-i+1$ 为 $gcd$ 的点也会相连

用并查集维护,再建立重构树,每次询问找到重构树上的瓶颈即可

比较裸的题但为什么就是想不出来!!!

如果你在 $2018.11.10$ 之前看到了这篇题解

祝 $NOIP2018$   $rp++$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5;
struct node
{
    int to,nxt;
}edge[N*20];
int n,m,num,head[N],cnt,f[N],tot[N],dep[N];
int tim,idx[N],top[N],fa[N],son[N],w[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]}; head[from]=num;
    edge[++num]=(node){from,head[to]}; head[to]=num;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void dfs(int k,int father,int deep)
{
    int bigson=0;
    fa[k]=father; dep[k]=deep; tot[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==father) continue;
        dfs(v,k,deep+1); tot[k]+=tot[v];
        if (bigson<tot[v]) bigson=tot[v],son[k]=v;
    }
}
void dfs(int k,int tp)
{
    idx[k]=++tim; top[k]=tp;
    if (!son[k]) return; dfs(son[k],tp);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!idx[v]) dfs(v,v);
    }
}
inline int getlca(int x,int y)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int main()
{
    n=cnt=read(),m=read();
    for (reg int i=1;i<=(n<<1);i++) f[i]=i;
    for (reg int i=m;i;i--)
    {
        for (reg int j=(i<<1);j<=n;j+=i)
        {
            int u=find(i),v=find(j);
            if (u==v) continue;
            w[f[u]=f[v]=++cnt]=m-i+1;
            add_edge(u,cnt); add_edge(v,cnt);
        }
    }
    dfs(cnt,0,1); dfs(cnt,cnt);
    for (reg int T=read();T;T--) printf("%d\n",w[getlca(read(),read())]);
    return 0;
}