| 记录编号 |
223842 |
评测结果 |
AAAAAAAAAAAAAAW |
| 题目名称 |
[WC 2006]水管局长数据加强版 |
最终得分 |
93 |
| 用户昵称 |
 /k |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
3.343 s |
| 提交时间 |
2016-02-13 21:32:16 |
内存使用 |
52.67 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
map<int,int>ma;
bool bbb[1000010];
int ff[100010];
int sta[1000010],tsta,pt;
inline int gf(int a)
{
if(a==ff[a])
return ff[a];
ff[a]=gf(ff[a]);
return ff[a];
}
inline void gj(int a,int b)
{
a=gf(a);
b=gf(b);
ff[a]=b;
}
int f[1100010];
int z[1100010];
int w[1100010];
int Z[1100010],Y[1100010],st[1100010];
int dy[1100010];
int r[1100010];
bool b[1100010];
struct u
{
int a;
int b;
int z;
}c[1000010];
inline bool gg(const u aa,const u bb)
{
return aa.z<bb.z;
}
struct uu
{
int k;
int a;
int b;
}qs[100010];
inline int in()
{
char ch = getchar();
for ( ; ch > '9' || ch < '0'; ch = getchar());
int tmp = 0;
for ( ; '0' <= ch && ch <= '9'; ch = getchar())
tmp = tmp * 10 + int(ch) - 48;
return tmp;
}
int n,m,Q;
int ns;
inline bool grt(int a)
{
return (f[a]==0||(Z[f[a]]!=a&&Y[f[a]]!=a));
}
inline void Pushdown(int a)
{
if(b[a])
{
b[a]=0;
b[Z[a]]^=1;
b[Y[a]]^=1;
swap(Z[a],Y[a]);
}
}
inline void Updata(int a)
{
z[a]=w[a];
r[a]=a;
if(Z[a])
{
if(z[a]<z[Z[a]])
{
r[a]=r[Z[a]];
z[a]=z[Z[a]];
}
}
if(Y[a])
{
if(z[a]<z[Y[a]])
{
r[a]=r[Y[a]];
z[a]=z[Y[a]];
}
}
}
inline void gy(int x)
{
int y=f[x];
int z=f[y];
if(Z[z]==y)
Z[z]=x;
else
if(Y[z]==y)
Y[z]=x;
f[x]=z;
f[Y[x]]=y;
Z[y]=Y[x];
f[y]=x;
Y[x]=y;
}
inline void gz(int x)
{
int xx=x;
int y=f[x];
int z=f[y];
//if(xx==796)
// printf("%d %d\n",f[796],z);
if(Z[z]==y)
Z[z]=x;
else
if(Y[z]==y)
Y[z]=x;
f[x]=z;
f[Z[x]]=y;
Y[y]=Z[x];
f[y]=x;
Z[x]=y;
}
inline void Splay(int x)
{
//printf("%d ",f[796]);
/* if(f[796]==796)
{
printf("GAME OVER");
while(1);
}*/
//printf("wrong %d\n",x);
int xx=x;
int y=x,t=1;
st[t]=y;
//printf("A");
while(!grt(y))
{
/*if(y==f[y]&&y==796)
{
printf("A%d %d ",y,f[y]);
//while(1);
}*/
//if(y==f[y])
// printf("%d ",y);
y=f[y];
st[++t]=y;
}
//printf("B");
for(int i=t;i>=1;i--)
Pushdown(st[i]);
for(int i=1;i<=t;i++)
Updata(st[i]);
while(!grt(x))
{
y=f[x];
if(Y[y]==x)
gz(x);
else
gy(x);
Updata(y);
Updata(x);
}
}
inline void Access(int x)
{
int t=0;
while(x)
{
Splay(x);
Y[x]=t;
Updata(x);
t=x;
x=f[x];
}
}
inline void Mroot(int a)
{
Access(a);
Splay(a);
b[a]^=1;
}
inline void Link(int father,int son)
{
Mroot(son);
f[son]=father;
}
inline void Cut(int father,int son)
{
//if(son==796||father==796)
// printf("GREAT");
//if(father==son)
// printf("WWW\n");
Mroot(son);
Access(father);
Splay(father);
f[son]=0;
Z[father]=0;
}
inline int gw(int aa,int bb)
{
Mroot(aa);
//printf("H%d ");
Access(bb);
Splay(aa);
//if(aa>n||bb>n)
// printf("E");
pt=r[Y[aa]];
w[0]=0;
/*if(pt<=n)
{
printf("WRONG%d ",Y[aa]);
while(1);
}*/
return z[Y[aa]];
}
inline void ggx(int a)
{
int i=ma[100000*qs[a].a+qs[a].b];
gw(c[i].a,c[i].b);
//printf("R%d\n",o);
if(c[i].z>=w[pt])
return;
int d=dy[pt];
//if(d==0)
// printf("WA");
Cut(c[d].a,pt);
Cut(pt,c[d].b);
++ns;
dy[ns]=i;
w[ns]=c[i].z;
Link(c[i].a,ns);
Link(ns,c[i].b);
}
int main()
{
freopen("tube_strong.in","r",stdin);
freopen("tube_strong.out","w",stdout);
n=in(),m=in(),Q=in();
ns=n;
for(int i=1;i<=m;i++)
{
c[i].a=in(),c[i].b=in(),c[i].z=in();
if(c[i].a>c[i].b)
swap(c[i].a,c[i].b);
}
sort(c+1,c+1+m,gg);
for(int i=1;i<=m;i++)
{
ma[c[i].a*100000+c[i].b]=i;
}
for(int i=1;i<=n;i++)
ff[i]=i;
for(int i=1;i<=Q;i++)
{
qs[i].k=in(),qs[i].a=in(),qs[i].b=in();
if(qs[i].a>qs[i].b)
swap(qs[i].a,qs[i].b);
if(qs[i].k==2)
bbb[ma[100000*qs[i].a+qs[i].b]]=1;
}
for(int i=1;i<=m;i++)
if(!bbb[i])
if(gf(c[i].a)!=gf(c[i].b))
{
gj(c[i].a,c[i].b);
++ns;
dy[ns]=i;
w[ns]=c[i].z;
Link(c[i].a,ns);
Link(ns,c[i].b);
}
//for(int i=1;i<=10;i++)
// printf("%d ",gw(1,4));
// printf("%d ",f[796]);
for(int i=Q;i>=1;i--)
{
if(qs[i].k==1)
{
sta[++tsta]=gw(qs[i].a,qs[i].b);
}
else
{
//printf("%d\n",Q);
ggx(i);
}
/*if(f[796]==796)
{
printf("%d ",qs[i].k);
while(1);
}*/
}
while(tsta)
printf("%d\n",sta[tsta--]);
//while(1);
getchar();
getchar();
}