uoj#349. 【WC2018】即时战略（动态点分治）

头一次看着题解有一种咱不会\(c++\)的感觉……

看题解吧……

//minamoto

#include<bits/stdc++.h>

#include "rts.h"

#define R register

#define get explore

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

const int N=3e5+5;const double alpha=0.75;

struct eg{int v,nx;}e[N<<1];int head[N],tot;

inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

int fa[N],fv[N],sz[N],msz[N],son[N],vis[N];

vector<int>id,now,S;map<int,int>G[N];

inline void addc(R int fat,R int u,R int v){fa[u]=fat,G[fat][v]=u,fv[u]=v;}

int size,rt,root,n;

void findrt(int u,int fat){

	sz[u]=1,son[u]=0;

	go(u)if(v!=fat&&!vis[v]){

		findrt(v,u),sz[u]+=sz[v];

		cmax(son[u],sz[v]);

	}

	cmax(son[u],size-sz[u]);

	if(son[u]<son[rt])rt=u;

}

void solve(int u){

	msz[u]=vis[u]=1;int p;

	go(u)if(!vis[v]){

		size=sz[v],rt=0,findrt(v,rt);

		p=rt,solve(rt),addc(u,p,v),msz[u]+=msz[p];

	}

}

void clr(int u){vis[u]=0;for(auto i:G[u])clr(i.second);G[u].clear();}

void re(int u){

	clr(u),size=msz[u],rt=0,findrt(u,0);

	if(u==root)root=rt,fa[rt]=0;else addc(fa[u],rt,fv[u]);

	solve(rt);

}

void find(int x){

	int u=root,v;now.clear(),S.clear();

	while(u!=x){

		v=get(u,x);

		if(!vis[v])add(u,v),add(v,u),addc(u,v,v),vis[v]=1,now.push_back(v);

		u=G[u][v],S.push_back(u);

	}

	for(int i:S)msz[fa[i]]-=msz[i];for(int i:now)msz[i]=1;

	for_each(S.rbegin(),S.rend(),[](int i){msz[fa[i]]+=msz[i];});

	for(int i:S)if(msz[i]>msz[fa[i]]*alpha)return re(fa[i]);

}

void chain(){

	int l=1,r=1;

	for(int i:id)if(!vis[i]){

		int x=get(l,i);

		if(vis[x])x=r,r=i;

		else l=i,vis[x]=1;

		while(x!=i)vis[x=get(x,i)]=1;

	}

}

void play(int _,int t,int ty){

	n=_,root=vis[1]=1,son[0]=N;fp(i,2,n)id.push_back(i);

	srand(time(0)),random_shuffle(id.begin(),id.end());

	if(ty==3)return chain();

	for(int i:id)if(!vis[i])find(i);

}

巴特西

uoj#349. 【WC2018】即时战略（动态点分治）

最新文章

热门文章