QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317401#7250. KornFroranzenTL 28ms15692kbC++143.3kb2024-01-28 22:48:182024-01-28 22:48:18

Judging History

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

  • [2024-01-28 22:48:18]
  • 评测
  • 测评结果:TL
  • 用时:28ms
  • 内存:15692kb
  • [2024-01-28 22:48:18]
  • 提交

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 = 2e5 + 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 ;
	}
}

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

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

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

input:

3 2
1 3
2 3

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 11ms
memory: 9364kb

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: 3ms
memory: 7200kb

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: 12ms
memory: 10096kb

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: 28ms
memory: 13268kb

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: 10ms
memory: 14364kb

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: 18ms
memory: 14348kb

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: 21ms
memory: 15512kb

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: 12ms
memory: 15396kb

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

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: 3ms
memory: 15012kb

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: 13ms
memory: 14308kb

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: 14ms
memory: 12744kb

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: -100
Time Limit Exceeded

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:


result: