IOI2014 game 交互题 构造题

题面
一道ioi的交互题，但并不是那么难。

最快代码752ms from ccz181078：

#include "game.h"
int mx,n,sz[4111],cnt[2111],log_2[2111];
void initialize(int _n){
    n=_n;
    for(mx=1;mx<=n;mx<<=1);
    for(int i=0;i<n;++i)sz[mx+i]=1;
    for(int i=mx-1;i;--i){
        int a=sz[i<<1],b=sz[i<<1|1];
        sz[i]=a+b;
        cnt[i]=a*b;
    }
    for(int i=1;i<mx;++i)log_2[i]=log_2[i>>1]+1;
}
int hasEdge(int u,int v){
    int w=u+mx>>log_2[u^v];
    return !--cnt[w];
}

Amazing！可以这么快！

另外一个很简单的做法（来自zxozxo）

#include "game.h"
void initialize(int n){}
int g[1505];
int hasEdge(int u,int v)
{
    if(u<v)u=v;
    return ++g[u]==u;
}

Amazing!可以这么短！

然而我写的方法是另一种又慢又丑又长又傻逼的做法。
显然要构造一个图。
每次询问u,v两点间连通性，计算u所在连通块中任意一点所能直接到达v所在连通块任意一点的边数，如果为1为了防止别的没有边就只能连了，否则就不连。
见代码。

#include "game.h"
int n;
int dtd[1505][1505],f[1505];
void initialize(int N) {
    n=N;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)dtd[i][j]=1;
        f[i]=i;
    }
}
int find(int u){
    return u==f[u]?u:f[u]=find(f[u]);
}
void merge(int u,int v){
    for(int i=1;i<=n;++i){
        dtd[u][i]+=dtd[v][i];
        dtd[i][u]+=dtd[i][v];
    }
    f[v]=u;
}
int hasEdge(int u,int v) {
    ++u;++v;
    u=find(u);
    v=find(v);
    if(dtd[u][v]-1){
        --dtd[u][v];
        --dtd[v][u];
        return 0;
    }
    merge(u,v);
    return 1;
}