QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178193#7250. KornPhantomThreshold#WA 1ms3644kbC++201.7kb2023-09-13 19:22:562023-09-13 19:22:56

Judging History

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

  • [2023-09-13 19:22:56]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3644kb
查看
  • [2023-09-13 19:22:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>> edges;
	vector<vector<int>> G(n+5);
	vector<int> deg(n+5);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edges.emplace_back(u,v);
		G[u].push_back(v);
		G[v].push_back(u);
		deg[u]++;deg[v]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(deg[i]%2!=0)
		{
			cout<<0<<endl;
			return 0;
		}
	}
	if(n==m)
	{
		cout<<n<<endl;
		for(int i=1;i<=n;i++)
			cout<<i<<' ';
		return 0;
	}
	vector<int> p(n+5),vis(n+5),dfn(n+5),cnt(n+5);
	int cyc=0,ind=0;
	function<void(int)> dfs=[&](int u)
	{
		dfn[u]=++ind;vis[u]=1;
		for(auto v:G[u])
		{
			if(p[u]==v)continue;
			if(not vis[v])
			{
				p[v]=u;
				dfs(v);
			}
			else if(vis[v]==1)
			{
				cyc++;
				if(cyc<=2)
				{
					int x=u;
					cnt[x]++;
					while(x!=v)
					{
						x=p[x];
						cnt[x]++;
					}
				}
			}
		}
		vis[u]=2;
	};
	dfs(1);
	vector<int> tmp,tmp2;
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==2)
		{
			tmp2.push_back(i);
		}
	}
	sort(tmp2.begin(),tmp2.end(),[&](int u,int v){return dfn[u]<dfn[v];});
	if(tmp2.size()==1u)tmp.push_back(tmp2[0]);
	else if(tmp2.size()>=2u)tmp.push_back(tmp2.front()),tmp.push_back(tmp2.back());
	vector<int> ans;
	auto check=[&](int d)
	{
		vector<int> pa(n+5);
		function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
		for(auto [u,v]:edges)
		{
			if(u==d or v==d)
				continue;
			int pu=find(u),pv=find(v);
			if(pu==pv)return false;
			pa[pv]=pu;
		}
		return true;
	};
	for(auto x:tmp)if(check(x))ans.push_back(x);
	cout<<ans.size()<<endl;
	for(auto z:ans)
	{
		cout<<z<<' ';
	}
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

6 8
3 5
5 1
3 4
4 1
6 3
1 6
2 3
1 2

output:

2
1 3

result:

ok 3 number(s): "2 1 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

3 3
1 2
2 3
3 1

output:

3
1 2 3

result:

ok 4 number(s): "3 1 2 3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

3 2
1 3
2 3

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

5 7
1 3
4 2
1 2
1 4
5 2
1 5
3 2

output:

2
1 2

result:

ok 3 number(s): "2 1 2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

5 5
5 3
1 5
2 1
4 2
3 4

output:

5
1 2 3 4 5

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

10 14
2 3
5 2
4 3
6 3
10 3
7 8
5 6
7 5
9 10
8 4
9 7
5 1
7 3
1 3

output:

1
3

result:

ok 2 number(s): "1 3"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

10 10
4 5
2 9
8 1
7 10
6 8
1 10
2 7
3 6
3 4
5 9

output:

10
1 2 3 4 5 6 7 8 9 10

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

10 16
1 6
9 8
9 3
5 1
1 2
4 1
2 9
7 9
9 4
1 8
9 5
1 3
9 6
10 9
1 10
1 7

output:

2
1 9

result:

ok 3 number(s): "2 1 9"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

100 168
53 8
35 44
98 64
28 85
35 62
95 11
41 62
46 12
73 62
28 49
31 66
84 61
38 70
60 13
69 67
44 62
35 77
9 36
39 62
52 27
50 87
38 24
4 62
16 88
94 37
46 62
100 90
98 4
19 78
52 55
54 91
32 62
52 51
5 14
80 41
24 62
20 15
11 1
22 62
69 62
72 62
29 62
38 62
90 62
56 30
58 18
40 62
89 38
12 62
70 ...

output:

1
62

result:

ok 2 number(s): "1 62"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

100 100
53 69
80 33
31 19
61 45
23 37
36 17
32 11
10 71
45 85
49 34
71 29
60 67
22 83
64 99
10 69
28 38
96 2
98 20
75 5
46 26
43 2
61 49
76 43
58 18
100 75
31 46
37 77
90 33
91 67
40 15
15 88
72 32
16 50
8 40
97 42
30 77
3 73
55 4
14 44
17 25
25 27
81 51
29 23
74 55
47 97
84 13
63 99
22 48
53 19
87 ...

output:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok 101 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 3480kb

input:

100 196
44 85
68 86
86 55
44 56
86 76
16 86
86 74
18 44
86 29
4 86
44 21
86 91
75 86
44 26
86 85
86 81
44 52
31 44
86 7
58 86
48 44
44 79
86 93
86 57
15 44
44 100
86 3
95 44
44 93
44 46
44 39
30 44
86 32
89 86
47 44
53 86
44 41
44 24
77 44
62 44
44 13
37 86
86 88
86 20
2 86
44 1
43 86
53 44
44 71
62...

output:

2
44 86

result:

ok 3 number(s): "2 44 86"

Test #13:

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

input:

1000 1636
85 954
434 807
657 942
363 998
200 942
570 258
147 942
231 455
655 942
730 784
257 942
514 590
62 674
197 975
553 831
186 410
454 435
62 966
292 798
83 440
114 942
2 287
230 209
770 220
64 206
536 366
670 942
354 425
151 942
173 942
179 529
8 942
56 324
931 904
898 444
650 493
567 669
797 ...

output:

1
942

result:

ok 2 number(s): "1 942"

Test #14:

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

input:

1000 1000
154 824
455 878
521 429
806 795
887 180
629 775
934 605
796 129
364 826
314 612
282 675
612 799
417 575
111 515
194 220
4 667
271 377
797 583
265 5
911 213
636 407
452 924
588 251
906 770
707 598
305 239
825 860
716 110
112 865
447 703
6 403
126 856
830 970
789 270
394 528
380 462
130 923
...

output:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok 1001 numbers

Test #15:

score: -100
Wrong Answer
time: 1ms
memory: 3580kb

input:

1000 1996
346 472
472 632
472 737
666 742
666 139
666 246
666 545
666 765
178 666
958 666
864 472
136 666
242 472
666 142
472 731
472 146
472 844
472 140
265 666
472 460
666 78
563 666
666 129
244 472
908 666
666 260
832 472
472 823
866 666
666 655
728 472
538 666
666 420
87 666
303 666
34 472
829 6...

output:

2
666 472

result:

wrong answer 2nd numbers differ - expected: '472', found: '666'
English 繁體中文 简体中文

伺服器時間: 2024-12-03 05:02:35 | 開源專案