QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317401 | #7250. Korn | Froranzen | TL | 28ms | 15692kb | C++14 | 3.3kb | 2024-01-28 22:48:18 | 2024-01-28 22:48:18 |
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 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;
}
Details
Tip: Click on the bar to expand more detailed information
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...