【WC2018】即时战略

动态淀粉质即可

#include "rts.h"
#include<algorithm>
#include<unordered_map>
#include<cstdlib>
#include<ctime>
#include<map>
const int maxn = 300300;
int per[maxn],vis[maxn];
typedef long long ll;
std::map<int,int> ans[maxn];
int N;
inline int get(int x,int y){
    return explore(x,y);
}
namespace list{
    const int LEFT=1,RIGHT=0;
    inline void solve(int to,int&l,int&r,int type=LEFT){
        if(l==to||r==to)return ;
        if(type == LEFT){
            int p=get(l,to);
            if(vis[p])solve(to,l,r,RIGHT);
            else vis[p]=1,solve(to,l=p,r,type);
        }else{
            int p=get(r,to);
            vis[p]=1,solve(to,l,r=p,type);
        }
    }
}
namespace wwj{
    int n;
    const double alpha=0.6;
    struct sol_tree{
        int size,rt;
        std::map<int,sol_tree*> son;
        inline sol_tree(int p){size=1,rt=p;}
        inline ~ sol_tree(){son.clear();}
    };
    struct T{int to,nxt;}way[maxn<<1];
    int h[maxn],num;
    inline void adde(int x,int y){
        way[++num]={y,h[x]},h[x]=num;
        way[++num]={x,h[y]},h[y]=num;
    }
    inline void up(int&x,int y){if(x<y)x=y;}
    sol_tree ** rebd;
    int vis[maxn];
    namespace dfz{
        int vis[maxn],size[maxn];
        inline void init(){for(int i=1;i<=n;++i)vis[i]=1;}
        inline void getsz(int x){
            vis[x]=size[x]=1;
            for(int i=h[x];i;i=way[i].nxt)
                if(!vis[way[i].to])getsz(way[i].to),size[x]+=size[way[i].to];
            vis[x]=0;
        }
        int rt,v;
        inline void getrt(int x,int al){
            vis[x]=1;
            int ms=0;
            for(int i=h[x];i;i=way[i].nxt)
                if(!vis[way[i].to])getrt(way[i].to,al),up(ms,size[way[i].to]);
            if(std::max(al-size[x],ms)<v)v=std::max(al-size[x],ms),rt=x;
            vis[x]=0;
        }
        inline int getroot(int x){getsz(x),v=1e9,getrt(x,size[x]);return rt;}
        inline sol_tree* sol(int x){
            x=getroot(x),vis[x]=1;
            sol_tree * ret = new sol_tree(x);
            for(int i=h[x];i;i=way[i].nxt)
                if(!vis[way[i].to]){
                    sol_tree * tmp=ret->son[way[i].to]=sol(way[i].to);
                    ret->size+=tmp->size;
                }
            return ret;
        }
        inline void dfscls(sol_tree * rt){
            vis[rt->rt] = 0;
            for(std::pair<int,sol_tree*>i:rt->son)
                dfscls(i.second);
            delete rt;
        }
    }
    int cnt,sumsz;
    inline void rebuild(sol_tree ** rebd){
        ++cnt;
        sol_tree* & rt = * rebd;
        int R = rt -> rt;sumsz+=rt->size;
        dfz::dfscls(rt);
        rt=dfz::sol(R);
    }
    inline int ins(sol_tree*&rt,int to){
        int p = get(rt -> rt,to);
        if(!vis[p]){
            sol_tree*&tmp=rt -> son[p] = new sol_tree(p);
            adde(rt -> rt,p),vis[p]=1;
            int res=0;
            if(p!=to)rt->size+=res=ins(tmp,to);
            if(rt -> size * alpha + 1 < tmp -> size)
                rebd =&rt;
            return res+1;
        }else{
            sol_tree*&tmp=rt->son[p];
            int res=0;
            rt->size+=res=ins(tmp,to);
            if(rt -> size * alpha + 1 < tmp -> size)
                rebd =&rt;
            return res;
        }
    }
    inline void solve(){
        srand(time(0));
        for(int i=1;i<=n;++i)per[i]=i;
        for(int i=1;i<=2;++i)std::random_shuffle(per+1,per+n+1);
        dfz::init();
        vis[1]=1;
        sol_tree * rt = new sol_tree(1);
        int cnt=n-1;
        while(cnt){
            int i=rand()%n+1;
            if(!vis[per[i]]){
                rebd=0;
                cnt-=ins(rt,per[i]);
                if(rebd)rebuild(rebd);
            }
        }
    }
}
void play(int n, int T, int dataType){
    N=wwj::n=n;
    if(dataType == 3){
        srand(time(0));
        for(int i=1;i<=n;++i)per[i]=i;
        for(int i=1;i<=10;++i)std::random_shuffle(per+1,per+n+1);
        vis[1]=1;
        for(int i=1,l=1,r=1;i<=n;++i)if(!vis[per[i]])
            list::solve(per[i],l,r);
    }else{
        wwj::solve();
    }
}