QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317402#7250. KornFroranzenRE 22ms27592kbC++143.3kb2024-01-28 22:50:012024-01-28 22:50:01

Judging History

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

  • [2024-01-28 22:50:01]
  • 评测
  • 测评结果:RE
  • 用时:22ms
  • 内存:27592kb
  • [2024-01-28 22:50:01]
  • 提交

answer

/*
尽可能减小问题规摸
分析必要条件,能不能得到充要条件
讨论最大/最小的元素的选择
想想简化的问题怎么做。或者是 x=0/x=1 这样的特殊情况。
拆贡献
容斥
分析答案上下界 
化简状态
正难则反
分析单调性,凸性
可以尝试网络流、高斯消元

专注,冷静。
*/
#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i) 
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef unsigned long long ull; 
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))  
#define mp(i, j) (make_pair(i, j))
// #define int long long
#define inf (int)(1e9+7)
#define INF 0x3f3f3f3f3f3f3f3f
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}
template<class I>
inline void read(I &x) {x = 0;I f = 1;char c = gc();while (c < '0' || c > '9') {if (c == '-') {f = -1;} c = gc();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc();}x *= f;}
template<class I>
inline void write(I x) {if (x == 0) {putchar('0');return;}I tmp = x > 0 ? x : -x;if (x < 0) {putchar('-');}int cnt = 0;while (tmp > 0) {buf1[cnt++] = tmp % 10 + '0';tmp /= 10;}while (cnt > 0)putchar(buf1[--cnt]);}
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')
} using namespace IO;
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
int sT;     


const int N = 4e5 + 5;
int n, m, u, v;

struct node {
	int to, nxt;
}e[N*5];

int head[N], cnt;

void add (int u ,int v) {
	e[++cnt] = (node){v, head[u]};
	head[u] = cnt;
}

int fath[N];
int deg[N];

int find (int u) {
	return (fath[u] == u) ? (u) : (fath[u] = find(fath[u]));
}

bool check (int lim) {
	re(i, n) fath[i] = i;
	re(u, n) {
		nx(i, u) {
			int v = e[i].to;
			if(u == lim || v == lim) continue;
			if(u < v) continue;
			int x = find(u), y = find(v);
			if(x == y) return 0;
			fath[x] = y;
		}
	}
	return 1;
}

vector<int>t1, t2, ans;
int cyc, vis[N],dfn[N], tot;

void dfs (int u, int fa) {
	vis[u] = 1;
	dfn[u] = ++tot;
	nx(i, u) {
		int v = e[i].to;
		if(v == fa) continue;
		if(!vis[v]) {
			fath[v] = u;
			dfs(v, u);
		}
		else if(vis[v] == 1) {
			int now = u;
			++cyc;
			while(now != v) {
				++deg[now];
				now = fath[now];
			}
			++deg[v];
		}
		if(cyc >= 2) return ;
	}
	vis[u] = 2;
}

int main () {
	read(n),read(m);
	re(i, m) {
		read(u),read(v);
		add(u,v),add(v, u);
		++deg[u], ++deg[v];
	}
	re(i, n) {
		if(deg[i] & 1) {
			puts("0");
			return 0;
		}
		deg[i] = 0;
	}
	if(n == m) {
		outn(n);
		re(i, n) {
			out(i);
		}
		return 0;
	}	
	dfs(1, 0);
	re(i, n) {
		if(deg[i] == 2) t1.pb(i);
	}
	sort(t1.begin(), t1.end(), [&](int u, int v){return dfn[u] < dfn[v];});
	int len = t1.size();
	if(len == 1) t2.pb(t1[0]);
	else t2.pb(t1[0]), t2.pb(t1[len-1]);
	for(int i : t2) if(check(i)) ans.pb(i);
	outn(ans.size());
	sort(ans.begin(), ans.end());
	for(int i : ans) {
		out(i);
	}
	return 0;
}	

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13988kb

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: 1ms
memory: 9864kb

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: 1ms
memory: 11920kb

input:

3 2
1 3
2 3

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

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: 1ms
memory: 11788kb

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: 1ms
memory: 11788kb

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: 2ms
memory: 13928kb

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: 1ms
memory: 11856kb

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: 2ms
memory: 13880kb

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: 13968kb

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: 9812kb

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: 2ms
memory: 13852kb

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: 0ms
memory: 14000kb

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: 9896kb

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: 0
Accepted
time: 1ms
memory: 13932kb

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
472 666 

result:

ok 3 number(s): "2 472 666"

Test #16:

score: 0
Accepted
time: 2ms
memory: 13960kb

input:

10000 16544
8723 5854
6694 5854
5813 9842
7775 450
5552 5854
2938 5854
4135 4252
195 5854
8773 3397
217 5854
6649 5854
5200 9200
4801 5854
7952 2026
7657 5854
1411 4257
4380 5854
307 5854
5880 8432
6556 5854
7178 4059
4188 3428
6602 5854
134 5854
1758 8587
2157 7784
1638 447
8039 1320
3848 5854
3185...

output:

1
5854 

result:

ok 2 number(s): "1 5854"

Test #17:

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

input:

10000 10000
6328 1933
3215 2119
133 597
5752 355
7264 8992
2759 8885
2141 1152
6369 553
8203 8771
9882 167
7977 1019
4924 3325
7006 2380
1669 8531
6813 3761
1904 7305
6037 5861
3036 8667
5650 9875
3979 4831
2967 4692
4652 5083
129 6518
635 1570
7543 4380
97 3534
5265 4098
9975 5326
1396 7440
3146 35...

output:

10000
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 10...

result:

ok 10001 numbers

Test #18:

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

input:

10000 19996
3251 3276
7746 2914
7968 3276
4133 3276
3276 8022
3276 7173
7524 3276
7746 4923
4310 7746
772 3276
7746 1759
7443 3276
8986 3276
7721 3276
2981 3276
7315 3276
3276 3539
2239 7746
3276 7321
3752 3276
8803 7746
3276 162
3276 5931
7746 1634
3276 7340
7746 6727
7746 5527
3825 7746
3276 309
3...

output:

2
3276 7746 

result:

ok 3 number(s): "2 3276 7746"

Test #19:

score: 0
Accepted
time: 9ms
memory: 16816kb

input:

100000 166466
48709 66850
19284 9360
70023 41035
10202 54726
2712 93277
34619 73662
52941 26348
68775 26348
8004 26348
56606 62430
7012 26348
72432 49283
63283 26348
91157 26348
20962 26348
48851 819
67562 33317
60982 54487
51298 26348
54608 26348
93406 15776
86876 36429
86195 63320
48011 87838
2770...

output:

1
26348 

result:

ok 2 number(s): "1 26348"

Test #20:

score: 0
Accepted
time: 5ms
memory: 14360kb

input:

100000 100000
13837 61303
89733 92564
27261 66328
53389 4963
22208 12832
66221 87293
57832 76651
26928 65552
32046 63821
33334 9211
22736 79922
78736 70685
46936 40767
11811 79863
57617 25991
31544 68117
439 19935
86061 23230
25277 26214
78618 37108
41744 862
97763 88227
24921 4418
12162 43160
99507...

output:

100000
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 1...

result:

ok 100001 numbers

Test #21:

score: 0
Accepted
time: 10ms
memory: 19280kb

input:

100000 199996
7841 69346
92805 7841
2391 7841
35715 86148
6555 7841
86148 54352
7841 58084
87454 86148
28044 7841
31135 86148
86148 37629
25497 86148
90738 7841
20885 7841
180 86148
7841 38081
40056 7841
86148 99814
59828 7841
86148 60395
47115 86148
7841 89824
7841 7595
7841 81503
69183 86148
38583...

output:

2
7841 86148 

result:

ok 3 number(s): "2 7841 86148"

Test #22:

score: 0
Accepted
time: 16ms
memory: 20104kb

input:

200000 333292
177495 59529
65976 27906
183521 63384
130253 63384
40480 63384
91014 63384
79387 36991
198564 153762
73533 110894
12944 108861
12238 63384
99881 63384
68989 97515
18802 166653
59172 121895
86970 63384
98223 63384
187114 63384
127440 63384
49766 63384
83238 63384
178656 127035
123780 17...

output:

1
63384 

result:

ok 2 number(s): "1 63384"

Test #23:

score: 0
Accepted
time: 9ms
memory: 18452kb

input:

200000 200000
172688 83121
94308 125397
121698 111684
122896 139134
39371 109248
102138 183415
5052 12685
39021 8297
159377 14034
116444 2183
103969 71784
83662 113890
108892 197485
150388 149939
30832 104502
37104 38939
169251 1170
143841 197835
104485 61831
40425 48553
33481 39125
180355 99424
192...

output:

200000
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 1...

result:

ok 200001 numbers

Test #24:

score: 0
Accepted
time: 22ms
memory: 20584kb

input:

200000 399996
195502 195302
97487 195502
31836 180762
31836 114578
195502 45901
195502 195976
31836 125928
105103 31836
105473 195502
14901 31836
31836 103081
22428 195502
23840 31836
150234 31836
195502 112065
175441 31836
31836 160616
53938 31836
92842 31836
59567 195502
68347 195502
31836 63589
1...

output:

2
31836 195502 

result:

ok 3 number(s): "2 31836 195502"

Test #25:

score: 0
Accepted
time: 16ms
memory: 18800kb

input:

199999 299997
133842 56831
161198 197552
52013 56831
113824 141089
101624 130455
56831 107334
22558 19119
178054 24475
62553 56831
61746 56831
133733 56831
106848 166983
56831 138717
24938 187178
94096 56831
56831 112384
56831 136917
160427 56831
56831 5750
56831 164172
56831 149425
37154 56831
1635...

output:

1
56831 

result:

ok 2 number(s): "1 56831"

Test #26:

score: 0
Accepted
time: 10ms
memory: 20036kb

input:

199966 266620
30805 74947
131498 74947
148055 45573
176247 144198
53354 86477
74947 126358
74947 107212
74947 49612
74947 42573
74947 110584
193627 9097
41516 120567
74947 56706
47810 17500
74947 10358
74947 102830
74947 176323
74947 108617
74947 152808
74947 180295
64264 43228
133818 74947
107407 7...

output:

1
74947 

result:

ok 2 number(s): "1 74947"

Test #27:

score: 0
Accepted
time: 13ms
memory: 20852kb

input:

199996 239994
194088 176928
84078 66003
155399 181267
109363 24037
192178 184529
65482 127386
165317 90199
15006 56197
192783 30629
109562 188336
184103 11211
3167 152299
118486 146019
109562 189171
109187 72056
118215 116281
172065 28419
196670 1865
1200 47868
16920 64834
10912 41425
157732 46848
1...

output:

1
109562 

result:

ok 2 number(s): "1 109562"

Test #28:

score: 0
Accepted
time: 9ms
memory: 18044kb

input:

199991 219989
26995 182816
44231 104797
66799 189612
60325 120474
104797 829
78882 151390
81503 14595
149710 27428
32075 83391
174714 104797
195813 94238
25539 103157
183556 23896
79477 48629
30469 84615
62113 167754
102224 63083
164838 81474
38093 93070
182007 172153
124803 72703
58411 94867
56180 ...

output:

1
104797 

result:

ok 2 number(s): "1 104797"

Test #29:

score: 0
Accepted
time: 9ms
memory: 19060kb

input:

199901 201899
183049 162042
30129 98024
109542 162807
165887 186046
137798 157485
38967 65020
13391 32948
22140 57753
20073 97624
8471 56387
122284 188507
164104 181767
8464 14667
198520 150207
49541 186950
177904 61052
101570 146445
57594 169884
190660 185995
64456 81911
183786 3956
133461 121730
1...

output:

1
174098 

result:

ok 2 number(s): "1 174098"

Test #30:

score: 0
Accepted
time: 8ms
memory: 18860kb

input:

199001 199199
190576 15936
195289 88100
62330 151921
85433 28871
125697 44401
152659 53914
24215 87572
26064 132643
19875 86105
38744 38509
187241 70599
95382 178764
71244 164377
397 87940
38361 142926
103135 60056
42490 160359
17113 91503
26575 1715
86209 190035
137871 114395
86611 3826
111584 3886...

output:

1
193563 

result:

ok 2 number(s): "1 193563"

Test #31:

score: 0
Accepted
time: 10ms
memory: 19080kb

input:

190001 190019
146460 136366
152584 71295
18424 74288
160666 4293
44055 39138
61552 85298
42372 68958
79305 92112
146894 169579
111049 26074
21458 89828
172108 49967
3434 7599
71150 177843
141351 189171
55126 35322
143057 109967
52416 180197
151751 88234
27577 27339
72702 31995
42469 88320
92311 5268...

output:

1
27520 

result:

ok 2 number(s): "1 27520"

Test #32:

score: 0
Accepted
time: 18ms
memory: 27592kb

input:

199999 200000
83463 54906
14939 155153
76174 149737
103606 118771
11573 199510
161888 142008
48833 125633
12953 52251
144814 144650
63226 137231
120524 156785
9290 62065
141977 109194
75981 9856
44547 118798
145907 20460
191163 88813
181023 105532
141868 119274
147782 181811
14243 124034
184303 1780...

output:

1
72170 

result:

ok 2 number(s): "1 72170"

Test #33:

score: 0
Accepted
time: 9ms
memory: 21800kb

input:

199999 250000
123656 75970
102071 118565
107227 44491
45664 44905
85395 132020
65851 150692
62090 130608
85787 190714
101502 115164
135646 124973
191194 123656
123656 31562
17137 123656
189830 107095
123656 178422
11051 161861
186977 123656
182905 123656
123656 83227
123656 182148
198064 105361
5055...

output:

1
123656 

result:

ok 2 number(s): "1 123656"

Test #34:

score: 0
Accepted
time: 10ms
memory: 19532kb

input:

198999 232000
42059 44655
32973 54440
47844 127864
146216 69825
54440 43480
83930 54440
103668 54440
147514 178713
9559 54440
125763 152701
77162 54440
4849 54146
176210 54440
113766 49606
46826 87343
68586 120698
41041 73987
122072 153479
88253 116764
196788 74978
91003 110326
161275 163198
157216 ...

output:

1
54440 

result:

ok 2 number(s): "1 54440"

Test #35:

score: 0
Accepted
time: 14ms
memory: 21292kb

input:

200000 343236
6172 121380
73997 136680
36608 38156
197529 31059
135022 82595
164816 111366
126315 132331
2397 82817
3410 55735
101524 41068
138146 106983
156410 60962
50402 188063
43797 154391
123183 120226
14173 67464
33393 65976
149359 114496
166968 169632
62051 89968
21074 75088
109977 39767
9743...

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 15ms
memory: 24132kb

input:

200000 449162
22188 74069
131951 149472
119926 72522
95032 63026
19474 72052
164476 74741
136119 117909
149064 43181
75663 56524
9948 92244
150899 26113
79619 40514
22197 148483
84712 82658
191039 103434
11219 150682
138136 93136
172480 89010
127153 14416
18014 75527
134240 19034
160149 97301
12535 ...

output:

0

result:

ok 1 number(s): "0"

Test #37:

score: -100
Runtime Error

input:

200000 449162
55595 43502
66495 49607
133565 22459
94162 167595
125087 87881
85874 138613
100034 37662
193243 59159
70523 122300
158914 15205
151322 180266
100094 22583
169537 132370
193557 109309
152075 91599
72716 181575
125888 51176
11319 110543
23393 76368
39201 165945
27744 123208
35061 46363
6...

output:


result: