QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61218#4818. Inverse Line GraphzhangfangwenWA 122ms19224kbC++144.0kb2022-11-11 16:01:282022-11-11 16:01:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 16:01:29]
  • 评测
  • 测评结果：WA
  • 用时：122ms
  • 内存：19224kb
查看
  • [2022-11-11 16:01:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
vector<int>g[300005];
int vist[300005];
int tt;
int a1[300005],a2[300005];
vector<int>vc;
int v[300005],tms=0;
void getall(int x){
	++tms;
	queue<int>q;
	q.emplace(x);
	v[x]=tms;
	while(q.size()){
		int x=q.front();
		vist[x]=1;
		q.pop();
		vc.emplace_back(x);
		for(auto cu:g[x]){
			if(v[cu]==tms)continue;
			v[cu]=tms;
			q.emplace(cu);
		}
	}
}
int cc[300005];
bool ranse(int x){
	if(a2[x])return 1;
	a2[x]=++tt;
	vector<int>lj;
	for(auto cu:g[x]){
		if(a1[cu]==a1[x]||a2[cu])continue;
		lj.emplace_back(cu);
	}
	for(auto cu:lj)++cc[cu];
	int gs=0;
	for(auto cu:lj){
		for(auto uc:g[cu]){
			if(cc[uc])++gs;
		}
	}
	for(auto cu:lj)--cc[cu];
	int sz=lj.size();
	if(gs!=1ll*sz*(sz-1))return 0;
	for(auto cu:lj){
		if(a1[cu])a2[cu]=tt;
		else a1[cu]=tt;
	}
	for(auto cu:lj){
		if(!a2[cu]){
			if(!ranse(cu))return 0;
		}
	}
	return 1;
}
bool test(int x,auto vc,auto s1,auto s2){
	for(auto cu:s1)cc[cu]=1;
	for(auto cu:s2)cc[cu]=2;
	int zh=0,mx=0;
	for(auto cu:s1){
		int gs=0;
		for(auto uc:g[cu]){
			if(cc[uc]==1)++zh;
			else if(cc[uc]==2)++gs;
		}
		mx=max(mx,gs);
	}
	for(auto cu:s2){
		int gs=0;
		for(auto uc:g[cu]){
			if(cc[uc]==2)++zh;
			else if(cc[uc]==1)++gs;
		}
		mx=max(mx,gs);
	}
	for(auto cu:s1)cc[cu]=0;
	for(auto cu:s2)cc[cu]=0;
	int n1=s1.size(),n2=s2.size();
	if(zh!=1ll*n1*(n1-1)+1ll*n2*(n2-1))return 0;
	if(mx>1)return 0;
	for(auto cu:vc)a1[cu]=a2[cu]=0;
	a1[x]=++tt,a2[x]=++tt;
	for(auto cu:s1)a1[cu]=a1[x];
	for(auto cu:s2)a1[cu]=a2[x];
	for(auto cu:s1)if(!ranse(cu))return 0;
	for(auto cu:s2)if(!ranse(cu))return 0;
	for(auto cu:vc){
		for(auto uc:g[cu]){
			if(a1[cu]!=a1[uc]){
				if(a1[cu]!=a2[uc]){
					if(a2[cu]!=a1[uc]){
						if(a2[cu]!=a2[uc]){
							return 0;
						}
					}
				}
			}
		}
	}
	return 1;
}
int bb[300005];
bool check(int x){
	vc.clear();
	getall(x);
	if((signed)vc.size()==1){
		a1[x]=++tt,a2[x]=++tt;
		return 1;
	}
	int p=g[x][0];
	vector<int>s1,s2;
	for(auto cu:g[x]){
		if(cu==p)s1.emplace_back(cu);
		else s2.emplace_back(cu);
	}
	if(test(x,vc,s1,s2))return 1;
	for(auto cu:g[x])++bb[cu];
	int q=0;
	for(auto cu:g[p]){
		if(bb[cu]){
			q=cu;
			break;
		}
	}
	for(auto cu:g[x])--bb[cu];
	if(!q)return 0;
	s1.clear(),s2.clear();
	for(auto cu:g[p])++bb[cu];
	for(auto cu:g[q])++bb[cu];
	for(auto cu:g[x]){
		if(cu==p||cu==q)s1.emplace_back(cu);
		else if(bb[cu]==2)s1.emplace_back(cu);
		else s2.emplace_back(cu);
	}
	for(auto cu:g[p])--bb[cu];
	for(auto cu:g[q])--bb[cu];
	if(test(x,vc,s1,s2))return 1;
	s1.clear(),s2.clear();
	int flag=1;
	for(auto cu:g[p])bb[cu]^=1;
	for(auto cu:g[q])bb[cu]^=2;
	for(auto cu:g[x]){
		if(cu==p)s1.emplace_back(cu);
		else if(cu==q)s2.emplace_back(cu);
		else if(bb[cu]==1)s1.emplace_back(cu);
		else if(bb[cu]==2)s2.emplace_back(cu);
		else{
			flag=0;
			break;
		}
	}
	for(auto cu:g[p])bb[cu]^=1;
	for(auto cu:g[q])bb[cu]^=2;
	if(!flag)return 0;
	if(test(x,vc,s1,s2))return 1;
	return 0;
}
int lg[600005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)g[i].clear();
		for(int i=1;i<=m;++i){
			int u,v;
			scanf("%d%d",&u,&v);
			g[u].emplace_back(v);
			g[v].emplace_back(u);
		}
		for(int i=1;i<=n;++i)vist[i]=0;
		tt=0;
		int flag=1;
		for(int i=1;i<=n;++i)if(!vist[i]){
			if(!check(i)){
				flag=0;
				break;
			}
		}
		if(T>60070)continue;
		if(T==60070){
			printf("%d %d\n",n,m);
			for(int i=1;i<=n;++i){
				for(auto cu:g[i]){
					if(cu>i)printf("%d %d\n",i,cu);
				}
			}
		}
		if(!flag)puts("No");
		else{
			puts("Yes");
			int l=0;
			for(int i=1;i<=n;++i){
				lg[++l]=a1[i],lg[++l]=a2[i];
			}
			sort(lg+1,lg+l+1);
			l=unique(lg+1,lg+l+1)-lg-1;
			printf("%d %d\n",l,n);
			for(int i=1;i<=n;++i){
				int A1=lower_bound(lg+1,lg+l+1,a1[i])-lg;
				int A2=lower_bound(lg+1,lg+l+1,a2[i])-lg;
				printf("%d %d\n",A1,A2);
			}
		}
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 17936kb

input:

6
5 6
1 2
1 3
1 4
3 4
2 5
4 5
1 0
2 1
1 2
3 3
1 2
1 3
2 3
4 3
1 2
1 3
1 4
5 6
1 2
2 3
2 4
3 4
3 5
4 5

output:

Yes
5 5
1 2
1 3
2 5
2 4
3 4
Yes
2 1
1 2
Yes
3 2
1 2
1 3
Yes
3 3
1 2
1 3
2 3
No
Yes
5 5
1 2
1 3
3 4
3 5
4 5

result:

ok that's great! (sum n = 20, sum m = 19) (6 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 19224kb

input:

5
6 5
3 4
1 6
1 5
2 5
5 6
2 0
1 0
5 3
2 3
3 4
2 4
6 4
5 6
4 5
1 6
2 4

output:

Yes
8 6
1 2
4 5
6 7
6 8
1 4
1 3
Yes
4 2
1 2
3 4
Yes
2 1
1 2
Yes
7 5
1 2
3 4
3 5
4 5
6 7
Yes
8 6
1 2
5 6
7 8
4 5
3 4
1 3

result:

ok that's great! (sum n = 20, sum m = 12) (5 test cases)

Test #3:

score: 0
Accepted
time: 7ms
memory: 17488kb

input:

14
5 3
2 5
1 5
1 2
4 3
2 4
1 2
1 3
5 6
2 3
1 5
4 5
2 4
1 2
1 3
3 0
6 5
3 4
1 5
2 6
5 6
2 3
4 4
1 2
3 4
1 4
2 3
6 7
1 3
5 6
3 6
1 2
3 5
1 6
2 6
1 0
5 5
1 2
2 4
2 5
3 5
4 5
4 0
2 0
3 0
1 0
1 0

output:

Yes
7 5
1 2
2 3
4 5
6 7
1 3
Yes
5 4
1 2
1 3
2 5
3 4
Yes
5 5
1 2
2 4
2 5
3 4
1 3
Yes
6 3
1 2
3 4
5 6
Yes
7 6
1 2
4 5
5 6
6 7
1 3
3 4
Yes
4 4
1 2
1 3
3 4
2 4
Yes
7 6
1 2
2 5
1 3
6 7
3 4
2 3
Yes
2 1
1 2
Yes
6 5
1 2
1 3
5 6
3 4
3 5
Yes
8 4
1 2
3 4
5 6
7 8
Yes
4 2
1 2
3 4
Yes
6 3
1 2
3 4
5 6
Yes
2 1
1 2
...

result:

ok that's great! (sum n = 50, sum m = 33) (14 test cases)

Test #4:

score: 0
Accepted
time: 6ms
memory: 19192kb

input:

5
5 3
2 3
1 2
2 5
9 12
2 6
2 5
3 5
3 4
5 8
2 8
6 9
4 7
1 9
1 8
7 9
1 6
2 0
5 3
4 5
1 3
3 4
2 1
1 2

output:

No
Yes
8 9
1 2
7 8
5 6
4 5
6 7
1 8
3 4
2 7
1 3
Yes
4 2
1 2
3 4
Yes
7 5
1 2
6 7
1 3
3 4
4 5
Yes
3 2
1 2
1 3

result:

ok that's great! (sum n = 23, sum m = 19) (5 test cases)

Test #5:

score: -100
Wrong Answer
time: 122ms
memory: 18176kb

input:

61395
7 0
1 0
5 1
1 2
3 1
1 3
7 11
2 4
2 5
1 6
5 7
1 4
1 5
2 7
3 7
1 2
3 5
4 5
9 10
2 7
4 5
5 9
1 8
1 3
2 6
6 7
2 4
3 7
6 8
1 0
8 10
2 6
6 8
1 4
1 8
4 6
2 4
2 3
1 2
4 8
1 3
9 12
3 7
4 7
7 9
1 6
3 8
2 5
5 9
3 4
4 6
4 8
5 7
7 8
6 5
2 6
1 2
4 5
2 3
1 3
3 1
1 2
2 0
1 0
4 2
1 2
2 4
3 3
1 2
2 3
1 3
1 0
9 ...

output:

6 9
1 6
1 4
1 2
2 3
2 4
2 6
3 4
3 6
4 6
Yes
6 6
1 2
1 4
3 4
1 4
5 6
1 3
Yes
4 2
1 2
3 4
Yes
6 4
1 2
5 6
2 4
1 3
Yes
6 5
1 2
1 3
4 5
4 6
1 4
Yes
10 8
1 2
3 8
3 4
3 7
1 3
4 5
9 10
5 6
Yes
6 5
1 2
3 5
1 6
3 4
1 3
Yes
9 7
1 2
6 7
1 3
3 4
4 5
2 4
8 9
Yes
9 6
1 2
4 5
6 7
1 3
4 6
8 9
Yes
11 8
1 2
4 5
1 3
8...

result:

wrong answer Integer parameter [name=m] equals to 1, violates the range [7, 7] (test case 1)
English 繁體中文 简体中文

Server Time: 2024-12-02 13:34:36 | OpenSource Project