QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317402 | #7250. Korn | Froranzen | RE | 22ms | 27592kb | C++14 | 3.3kb | 2024-01-28 22:50:01 | 2024-01-28 22:50:01 |
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 = 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...