uoj#274. 【清华集训2016】温暖会指引我们前行（LCT）

不难发现肯定是在温度的最大生成树上走是最优的

于是用\(LCT\)维护最大生成树，每一次加边时如果已经连通，就判断一下路径上的最小温度是否小于当前温度，是的话就断掉那条边，加入新边

//minamoto

#include<bits/stdc++.h>

#define R register

#define fi first

#define se second

#define pi pair<int,int>

#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)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

inline char getop(){char ch;while((ch=getc())!='f'&&ch!='m'&&ch!='c');return ch;}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=4e5+5;

int ch[N][2],fa[N],v[N],sum[N],f[N],w[N],px[N],py[N];bool rev[N];pi mn[N];

int n,m,id,x,y,t,l,zz;char op;

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

inline bool is(R int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

void upd(R int x){

	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+w[x];

	mn[x]=min(pi(v[x],x),min(mn[ch[x][0]],mn[ch[x][1]]));

}

inline void ppd(R int x){swap(ch[x][0],ch[x][1]),rev[x]^=1;}

inline void pd(R int x){if(rev[x])ppd(ch[x][0]),ppd(ch[x][1]),rev[x]=0;}

void update(R int x){if(!is(x))update(fa[x]);pd(x);}

void rotate(int x){

	int y=fa[x],z=fa[y],d=ch[y][1]==x;

	if(!is(y))ch[z][ch[z][1]==y]=x;

	fa[x]=z,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y,fa[y]=x,upd(y);

}

void splay(int x){

	update(x);

	for(R int y=fa[x],z=fa[y];!is(x);y=fa[x],z=fa[y]){

		if(!is(y))(ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);

		rotate(x);

	}upd(x);

}

inline void access(int x){

	int t=0;

	while(x)splay(x),ch[x][1]=t,upd(x),t=x,x=fa[x];

}

inline void makert(int x){

	access(x),splay(x),ppd(x);

}

inline void split(int x,int y){

	makert(x),access(y),splay(y);

}

inline void link(int x,int y){

	makert(x),fa[x]=y;

}

inline void cut(int x,int y){

	split(x,y),fa[x]=ch[y][0]=0,upd(y);

}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read();

	mn[0]=pi(1<<30,0);

	fp(i,1,n)f[i]=i,v[i]=1<<30,mn[i]=pi(v[i],i);

	while(m--){

		op=getop();

		switch(op){

			case 'f':{

				id=read()+1,x=read()+1,y=read()+1,t=read(),l=read();

				v[id+n]=t,sum[id+n]=w[id+n]=l,mn[id+n]=pi(v[id+n],id+n);

				px[id]=x,py[id]=y;

				if(find(x)!=find(y))link(id+n,x),link(id+n,y),f[f[x]]=f[y];

				else{

					split(x,y);

					if(mn[y].fi<t){

						zz=mn[y].se-n,cut(zz+n,px[zz]),cut(zz+n,py[zz]);

						link(id+n,x),link(id+n,y);

					}

				}

				break;

			}

			case 'm':{

				x=read()+1,y=read()+1;

				if(find(x)!=find(y))print(-1);

				else split(x,y),print(sum[y]);

				break;

			}

			case 'c':{

				id=read()+1,l=read();

				splay(id+n),w[id+n]=l,upd(id+n);

				break;

			}

		}

	}return Ot(),0;

}

巴特西

uoj#274. 【清华集训2016】温暖会指引我们前行（LCT）

最新文章

热门文章