| 记录编号 |
461764 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[AHOI 2005] LANE 航线规划 |
最终得分 |
100 |
| 用户昵称 |
 wangxh |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.409 s |
| 提交时间 |
2017-10-20 17:31:38 |
内存使用 |
21.99 MiB |
显示代码纯文本
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define pa pair<int,int>
#define mmin(a,b) (a<b?a:b)
struct tree{
int u,v,next,d;
}l1[301000];
struct tree2{
int u,v,next;
}l2[201000];
struct tree3{
int le,ri,d;
}l3[801000];
map<pa,int> ma;
int n,m,lian[201000],e,dfn[30100],low[30100],yan[800100];
int be[30100],cnt,k,num,st[30100],head,cnt2;
int q0[40100],q1[40100],q2[40100],ans[40100];
int fa[30100],size[30100],son[30100],dep[30100],top[30100],dfn2[30100];
bool pd[40100];
void bian(int,int);
void tar(int,int);
void bian2(int,int);
void dfs(int);
void dfs2(int,int);
void build(int,int,int);
void pou1(int,int);
void change(int,int,int);
void pushdown(int);
void pou2(int,int);
int query(int,int,int);
int main()
{
// freopen("in.txt","r",stdin);
freopen("lane.in","r",stdin);
freopen("lane.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
bian(x,y);
bian(y,x);
}
int opt;
while(1)
{
scanf("%d",&opt);
if(opt==-1) break;
++k;
q0[k]=opt;
scanf("%d%d",&q1[k],&q2[k]);
if(opt==0) ma[(pa){q1[k],q2[k]}]=1,ma[(pa){q2[k],q1[k]}]=1;
}
tar(1,0);
int cun=e;
memset(lian,0,sizeof(lian));
e=0;
for(int i=1;i<=cun;i++)
{
int u=l1[i].u,v=l1[i].v;
if(ma.count((pa){u,v})==1) continue;
u=be[u];v=be[v];
if(u!=v)
bian2(u,v);
}
dfs(1);
dfs2(1,1);
build(1,cnt,1);
for(int i=k;i>=1;i--)
{
if(q0[i]==0) pou1(be[q1[i]],be[q2[i]]);
else pou2(be[q1[i]],be[q2[i]]);
}
for(int i=ans[0];i>=1;i--) printf("%d\n",ans[i]);
return 0;
}
void bian(int x,int y)
{
e++;
l1[e].u=x;
l1[e].v=y;
l1[e].next=lian[x];
lian[x]=e;
}
void tar(int x,int y)
{
pd[x]=1;
st[++head]=x;
dfn[x]=low[x]=++num;
for(int i=lian[x];i;i=l1[i].next)
{
int v=l1[i].v;
if(v==y) continue;
if(ma.count((pa){x,v})==1) continue;
if(dfn[v]==0)
{
tar(v,x);
low[x]=mmin(low[v],low[x]);
}
else
if(pd[v]==1)
low[x]=mmin(dfn[v],low[x]);
}
if(dfn[x]==low[x])
{
++cnt;
int temp;
while(1)
{
temp=st[head];--head;
pd[temp]=0;
be[temp]=cnt;
if(temp==x) break;
}
}
}
void bian2(int x,int y)
{
e++;
l2[e].u=x;
l2[e].v=y;
l2[e].next=lian[x];
lian[x]=e;
}
void dfs(int x)
{
size[x]=1;
for(int i=lian[x];i;i=l2[i].next)
{
int v=l2[i].v;
if(v!=fa[x])
{
fa[v]=x;
dep[v]=dep[x]+1;
dfs(v);
size[x]+=size[v];
if(size[son[x]]>size[v])
son[x]=v;
}
}
}
void dfs2(int x,int y)
{
dfn2[x]=++cnt2;
top[x]=y;
if(son[x]!=0)
dfs2(son[x],y);
for(int i=lian[x];i;i=l2[i].next)
{
int v=l2[i].v;
if(fa[x]!=v&&v!=son[x])
dfs2(v,v);
}
}
void build(int le,int ri,int i)
{
l3[i].le=le;
l3[i].ri=ri;
if(le==ri)
{
l3[i].d=1;
return;
}
int mid=(le+ri)>>1;
build(le,mid,i*2);
build(mid+1,ri,i*2+1);
l3[i].d=l3[i*2].d+l3[i*2+1].d;
}
void pou1(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(x,y);
swap(fx,fy);
}
change(dfn2[fx],dfn2[x],1);
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
if(dep[x]!=dep[y]) change(dfn2[x]+1,dfn2[y],1);
}
void change(int le,int ri,int i)
{
if(l3[i].le==le&&l3[i].ri==ri)
{
l3[i].d=0;
yan[i]=1;
return;
}
pushdown(i);
int mid=(l3[i].le+l3[i].ri)>>1;
if(ri<=mid) change(le,ri,i*2);
else if(le>mid) change(le,ri,i*2+1);
else change(le,mid,i*2),change(mid+1,ri,i*2+1);
l3[i].d=l3[i*2].d+l3[i*2+1].d;
}
void pushdown(int i)
{
if(yan[i]!=0)
{
yan[i*2]=yan[i*2+1]=1;
yan[i]=0;
l3[i*2].d=0;
l3[i*2+1].d=0;
}
}
void pou2(int x,int y)
{
int fx=top[x],fy=top[y],sum=0;
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(x,y);
swap(fx,fy);
}
sum+=query(dfn2[fx],dfn2[x],1);
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
if(dep[x]!=dep[y]) sum+=query(dfn2[x]+1,dfn2[y],1);
ans[++ans[0]]=sum;
}
int query(int le,int ri,int i)
{
if(l3[i].le==le&&l3[i].ri==ri) return l3[i].d;
int mid=(l3[i].le+l3[i].ri)>>1;
if(ri<=mid) return query(le,ri,i*2);
else if(le>mid) return query(le,ri,i*2+1);
else return query(le,mid,i*2)+query(mid+1,ri,i*2+1);
}