QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317387 | #7250. Korn | Froranzen | WA | 27ms | 35112kb | C++14 | 2.7kb | 2024-01-28 22:09:57 | 2024-01-28 22:09:59 |
Judging History
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);
}
Details
Tip: Click on the bar to expand more detailed information
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'