用的边带权并查集,但40分,求调玄关
  • 板块P10686 Rochambeau
  • 楼主lzdll
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/11 22:18
  • 上次更新2024/12/11 22:26:50
查看原帖
用的边带权并查集,但40分,求调玄关
925129
lzdll楼主2024/12/11 22:18
#include<bits/stdc++.h>
#define int long long
#define N 505
using namespace std;
int n,m;
int fa[N],d[N],sz[N];
int Find(int x){
	if(x==fa[x])return x;
	int root=Find(fa[x]);
	d[x]=d[x]+d[fa[x]];
	d[x]=(d[x]+3000)%3;
	fa[x]=root;
	return root;
}
struct node{
	int a,b,c;
}q[2005];
signed main(){
	while(cin>>n>>m){
		for(int i=1;i<=m;++i){
			char c;
			cin>>q[i].a>>c>>q[i].b;
			if(c=='=')q[i].c=0;
			else if(c=='<')q[i].c=2;
			else q[i].c=1;
		}
		int cnt=0,ans=-2010;
		for(int k=0;k<n;++k){
			for(int i=0;i<n;++i){
				fa[i]=i,d[i]=0,sz[i]=1;
			}
			//meiju who is judger
			bool flag=1;
			for(int i=1;i<=m;++i){
				if(q[i].a==k||q[i].b==k)continue;
				int a=q[i].a,b=q[i].b,c=q[i].c;
				if(Find(a)!=Find(b)){
					d[Find(a)]+=c-d[a]+d[b];
					d[Find(a)]=(d[Find(a)]+300)%3;
					fa[a]=b;
				}else{
					if((d[a]-d[b]+300)%3!=c){
						flag=0;
						break;
					}
				}
			}
			if(flag){
				++cnt;
				ans=k;
			}
			if(k==1){
//				for(int i=0;i<n;++i){
//					cout<<d[i]<<" ";
//				}
			}
		}
		if(cnt==0){
			cout<<"Impossible\n";
		}else if(cnt==1){
			cout<<"Player "<<ans<<" can be determined to be the judge after ";
			for(int i=0;i<n;++i){
				fa[i]=i,d[i]=0,sz[i]=1;
			}	
			int as=0;
			bool vis[505]={0};
			int ct=0;
			for(int i=1;i<=m;++i){
				int a=q[i].a,b=q[i].b,c=q[i].c;
				if(Find(a)!=Find(b)){
					d[Find(a)]+=c-d[a]+d[b];
					d[Find(a)]=(d[Find(a)]+30000)%3;
					fa[a]=b;
				}else{
					if((d[a]-d[b]+30000)%3!=c){
						if(vis[b]==0){
							vis[b]=1,++ct;
						}
						if(vis[a]==0){
							vis[a]=1,++ct;
						}
						if(ct>=3){
							as=i;
							break;
						}
					}
				}
			}
			cout<<as<<" lines\n";
		}else{
			cout<<"Can not determine\n";
		}
	}
	return 0;
}

Only AC on #1 #2 #5 #8

2024/12/11 22:18
加载中...