Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC code

Posted by 2016gdgzoi471 at 2017-08-08 22:10:12 on Problem 2831
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005,M=100005;
int n,m,t,u,v,w,cnt,tot,head[N],nxt[2*N],to[2*N],d[2*N],fa[N],dep[N],siz[N],son[N],pos[N],top[N],maxv[N*4];
bool flag=false;
struct edge
{
	int u,v,dis,od;
	bool use;
}e[M];
void adde(int u,int v,int w)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	d[cnt]=w;
	head[u]=cnt;
}
bool cmp(edge a,edge b)
{
	return a.dis<b.dis;
}
bool cmp2(edge a,edge b)
{
	return a.od<b.od;
}
int find(int u)
{
	return u==fa[u]?u:fa[u]=find(fa[u]);
}
void init()
{
	cnt=tot=0;
	memset(son,-1,sizeof(son));
	memset(maxv,0,sizeof(maxv));
	memset(head,0,sizeof(head));
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		e[i].use=false;
	}
}
void dfs1(int pre,int u,int d)
{
	fa[u]=pre;
	dep[u]=d;
	siz[u]=1;
	for(int v=head[u];v;v=nxt[v])
		if(to[v]^fa[u])
		{
			dfs1(u,to[v],d+1);
			if(son[u]==-1||siz[to[v]]>siz[son[u]])
				son[u]=to[v];
			siz[u]+=siz[to[v]];
		}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	pos[u]=++tot;
	if(son[u]==-1) return;
	dfs2(son[u],tp);
	for(int v=head[u];v;v=nxt[v])
		if(to[v]^fa[u]&&to[v]^son[u])
			dfs2(to[v],to[v]);
}
void update(int o,int x,int l,int r,int k)
{
	if(l==r)
	{
		maxv[o]=x;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) update(o*2,x,l,mid,k);
	else update(o*2+1,x,mid+1,r,k);
	maxv[o]=max(maxv[o*2],maxv[o*2+1]);
}
int query(int o,int l,int r,int L,int R)
{
	if(L<=l&&R>=r) return maxv[o];
	int mid=(l+r)/2,ans=0;
	if(L<=mid) ans=max(ans,query(o*2,l,mid,L,R));
	if(R>mid) ans=max(ans,query(o*2+1,mid+1,r,L,R));
	return ans;
}
int Query(int u,int v)
{
	int f1=top[u],f2=top[v],ans=0;
	while(f1!=f2)
	{
		if(dep[f1]<dep[f2])
		{
			swap(f1,f2);
			swap(u,v);
		}
		ans=max(ans,query(1,1,n,pos[f1],pos[u]));
		u=fa[f1];
		f1=top[u];
	}
	if(u==v) return ans;
	if(dep[u]>dep[v]) swap(u,v);
	return max(ans,query(1,1,n,pos[son[u]],pos[v]));
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&t))
	{
		init();
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			e[i].u=u;
			e[i].v=v;
			e[i].dis=w;
			e[i].od=i;
		}
		sort(e+1,e+m+1,cmp);
		for(int i=1;i<=m;i++)
		{
			u=find(e[i].u),v=find(e[i].v);
			if(u!=v)
			{
				fa[v]=u;
				adde(e[i].u,e[i].v,w);
				adde(e[i].v,e[i].u,w);
				tot++;
				e[i].use=true;
				if(tot==n-1)
				{
					flag=true;
					break;
				}
			}
		}
		sort(e+1,e+m+1,cmp2);
		memset(fa,0,sizeof(fa));
		tot=0;
		dfs1(0,1,0);
		dfs2(1,1);
		for(int i=1;i<=m;i++)
			if(e[i].use)
			{
				if(dep[e[i].u]<dep[e[i].v])
					swap(e[i].u,e[i].v);
				update(1,e[i].dis,1,n,pos[e[i].u]);
			}
		for(int i=1;i<=t;i++)
		{
			scanf("%d%d",&u,&v);
			puts(Query(e[u].u,e[u].v)>=v?"Yes":"No");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator