QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317387#7250. KornFroranzenWA 27ms35112kbC++142.7kb2024-01-28 22:09:572024-01-28 22:09:59

Judging History

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

  • [2024-01-28 22:09:59]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:35112kb
  • [2024-01-28 22:09:57]
  • 提交

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 low[N], dfn[N], sta[N], top, vis[N], tot;

void upd (int u) {
	vis[u] = 0; --top;
}

int deg[N];
vector<int>vec;
int f[N];

void tarjan (int u, int fa) {
	low[u] = dfn[u] = ++tot;
	sta[++top] = u; vis[u] = 1;
	nx(i, u) {
		int v = e[i].to;
		if(v == fa) continue;
		if(!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] <= dfn[u]) ++f[u];
		}
		else if(vis[v]) {
			low[u] = min(low[u], dfn[v]);
			++f[u];
		}
	}
}

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;
		}
	}
	tarjan(1, 0);
	--f[1];
	re(i, n) if(f[i] == m - n + 1) vec.pb(i);
	outn(vec.size());
	sort(vec.begin(), vec.end());
	for(int i : vec) out(i);
}

詳細信息

Test #1:

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

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

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

input:

3 2
1 3
2 3

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 9ms
memory: 21260kb

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

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

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: 27ms
memory: 35112kb

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: 15ms
memory: 21092kb

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: -100
Wrong Answer
time: 14ms
memory: 18920kb

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:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'