C++14(g++5.4) 解法, 执行用时: 677ms, 内存消耗: 5752K, 提交时间: 2019-04-16 21:09:39
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,t,k,opt,x,y,z,root,c;
int zhan[N],val[N],fa[10][N],ans[10][N],tag[10][N],d[10][N],ch[10][N][2];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;
char c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
ret=ret*10+c-48;
c=gc();
}
if(f)return -ret;
return ret;
}
bool chk(int c,int u)
{
return ch[c][fa[c][u]][1]==u;
}
bool pd(int c,int u)
{
return ch[c][fa[c][u]][0]==u||ch[c][fa[c][u]][1]==u;
}
void pushup(int c,int x)
{
ans[c][x]=max(ans[c][ch[c][x][0]],max(ans[c][ch[c][x][1]],val[x]));
}
void pushdown(int c,int x)
{
int l=ch[c][x][0],r=ch[c][x][1];
if(tag[c][x])
{
if(l)
{
swap(ch[c][l][0],ch[c][l][1]);
tag[c][l]^=1;
}
if(r)
{
swap(ch[c][r][0],ch[c][r][1]);
tag[c][r]^=1;
}
tag[c][x]=0;
}
}
void Zhuan(int c,int x)
{
int y=fa[c][x],z=fa[c][y],k=chk(c,x),w=ch[c][x][k^1];
if(pd(c,y))ch[c][z][chk(c,y)]=x;
ch[c][x][k^1]=y,ch[c][y][k]=w;
if(w)fa[c][w]=y;fa[c][y]=x,fa[c][x]=z;
pushup(c,y);pushup(c,x);
}
void splay(int c,int x)
{
int y=x,top=0;
zhan[++top]=y;
while(pd(c,y))zhan[++top]=y=fa[c][y];
while(top)pushdown(c,zhan[top--]);
while(pd(c,x))
{
y=fa[c][x];
if(pd(c,y))
{
if(chk(c,x)==chk(c,y))Zhuan(c,y);
else Zhuan(c,x);
}
Zhuan(c,x);
}
pushup(c,x);
return;
}
void access(int c,int x)
{
for(int y=0;x;y=x,x=fa[c][x])
{
splay(c,x);
ch[c][x][1]=y;
pushup(c,x);
}
}
void makeroot(int c,int x)
{
access(c,x);splay(c,x);
swap(ch[c][x][0],ch[c][x][1]);
tag[c][x]^=1;
}
int findroot(int c,int x)
{
access(c,x);splay(c,x);
while(ch[c][x][0])x=ch[c][x][0];
splay(c,x);
return x;
}
void split(int c,int x,int y)
{
makeroot(c,x);
access(c,y);splay(c,y);
}
void link(int c,int x,int y)
{
d[c][x]++;
d[c][y]++;
makeroot(c,x);
fa[c][x]=y;
}
void cut(int c,int x,int y)
{
d[c][x]--;
d[c][y]--;
split(c,x,y);
fa[c][x]=ch[c][y][0]=0;
}
void dian(int c)
{
int x=read(),y=read();
for(int i=0;i<c;i++)
{
access(i,x);
splay(i,x);
}
val[x]=y;
for(int i=0;i<c;i++)pushup(i,x);
}
void bian(int c)
{
int u=read(),v=read(),w=read();
for(int i=0;i<c;i++)
if(findroot(i,u)==findroot(i,v))
{
split(i,u,v);
if(ch[i][v][0]!=u||ch[i][u][1])continue;
if(i==w)
{
puts("Success.");
return;
}
if((d[w][u]==2)||(d[w][v]==2))
{
puts("Error 1.");
return;
}
else if(findroot(w,u)==findroot(w,v))
{
puts("Error 2.");
return;
}
else{
cut(i,u,v);link(w,u,v);
puts("Success.");
return;
}
}
puts("No such edge.");
}
void query()
{
int c=read(),u=read(),v=read();
if(findroot(c,u)!=findroot(c,v))
{
puts("-1");
return;
}
split(c,u,v);
printf("%d\n",ans[c][v]);
}
int main()
{
n=read();m=read();c=read();k=read();
for(int i=1;i<=n;i++)val[i]=read();
while(m--)
{
int x=read(),y=read(),z=read();
link(z,x,y);
}
while(k--)
{
int opt=read();
if(opt==0)dian(c);
else if(opt==1)bian(c);
else if(opt==2)query();
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 515ms, 内存消耗: 9080K, 提交时间: 2019-03-16 12:23:17
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int
N=10005,
M=100005;
int n,m,C,K;
int v[N],stk[N];
struct Edge{
int u,v;
bool operator <(Edge x)const{
if (x.u!=u) return x.u>u;
else return x.v>v;
}
};
map<Edge,int>E;
struct LinkCutTree{
int pre[N],son[N][2],Max[N],cnt[N];
bool rev[N];
bool isroot(int x){
return son[pre[x]][0]!=x &&
son[pre[x]][1]!=x;
}
void up(int x){
Max[x]=v[x];
int l=son[x][0],r=son[x][1];
Max[x]=max(Max[l],max(Max[x],Max[r]));
}
void down(int x){
if (rev[x]){
int l=son[x][0],r=son[x][1];
swap(son[x][0],son[x][1]);
rev[l]^=1,rev[r]^=1,rev[x]^=1;
}
}
void Rotate(int x){
int y=pre[x],z=pre[y],l,r;
if (son[y][0]==x) l=0; else l=1;
r=l^1;
if (!isroot(y))
if (son[z][0]==y) son[z][0]=x;
else son[z][1]=x;
pre[x]=z; pre[y]=x;
pre[son[x][r]]=y;
son[y][l]=son[x][r];
son[x][r]=y; up(y);
}
void splay(int x){
int y,z,top=0;
stk[++top]=x;
for (int i=x;!isroot(i);i=pre[i])
stk[++top]=pre[i];
while (top) down(stk[top--]);
while (!isroot(x)){
y=pre[x],z=pre[y];
if (!isroot(y))
if (son[y][0]==x^son[z][0]==y) Rotate(x);
else Rotate(y);
Rotate(x);
}
up(x);
}
void access(int x){
for (int y=0;x;y=x,x=pre[x])
splay(x),son[x][1]=y,up(x);
}
void makeroot(int x){
access(x),splay(x);
rev[x]^=1;
}
void split(int x,int y){
makeroot(x);
access(y),splay(y);
}
int findroot(int x){
access(x),splay(x);
while (son[x][0]) x=son[x][0];
return x;
}
bool sameset(int x,int y){
return findroot(x)==findroot(y);
}
void cut(int x,int y){
split(x,y);
cnt[x]--,cnt[y]--;
pre[x]=son[y][0]=0;
up(y);
}
void link(int x,int y){
makeroot(x);
cnt[x]++,cnt[y]++;
pre[x]=y;
}
int querymax(int x,int y){
split(x,y);
return Max[y];
}
}LCT[15];
int main(){
n=read(),m=read(),C=read(),K=read();
for (int i=1;i<=n;i++) v[i]=read();
int opt,x,y,w; Edge t1;
while (m--){
x=read(),y=read(),w=read();
if (x>y) swap(x,y);
t1=(Edge){x,y},E[t1]=w;
LCT[w].link(x,y);
}
while (K--){
opt=read();
if (!opt){
x=read(),y=read();
v[x]=y;
for (int i=0;i<C;i++) LCT[i].splay(x);
} else
if (opt==1){
x=read(),y=read(),w=read();
if (x>y) swap(x,y);
t1=(Edge){x,y};
if (!E.count(t1)){
puts("No such edge.");
continue;
}
if (E[t1]==w){
puts("Success.");
continue;
}
if (LCT[w].cnt[x]>=2 || LCT[w].cnt[y]>=2){
puts("Error 1.");
continue;
}
if (LCT[w].sameset(x,y)){
puts("Error 2.");
continue;
}
puts("Success.");
int tmp=E[t1];
LCT[tmp].cut(x,y),LCT[w].link(x,y);
E[t1]=w;
t1=(Edge){y,x}; E[t1]=w;
} else{
w=read(),x=read(),y=read();
if (x==y) printf("%d\n",v[x]);
else
if (!LCT[w].sameset(x,y))
puts("-1"); else
printf("%d\n",LCT[w].querymax(x,y));
}
}
return 0;
}