QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178193 | #7250. Korn | PhantomThreshold# | WA | 1ms | 3644kb | C++20 | 1.7kb | 2023-09-13 19:22:56 | 2023-09-13 19:22:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<pair<int,int>> edges;
vector<vector<int>> G(n+5);
vector<int> deg(n+5);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
edges.emplace_back(u,v);
G[u].push_back(v);
G[v].push_back(u);
deg[u]++;deg[v]++;
}
for(int i=1;i<=n;i++)
{
if(deg[i]%2!=0)
{
cout<<0<<endl;
return 0;
}
}
if(n==m)
{
cout<<n<<endl;
for(int i=1;i<=n;i++)
cout<<i<<' ';
return 0;
}
vector<int> p(n+5),vis(n+5),dfn(n+5),cnt(n+5);
int cyc=0,ind=0;
function<void(int)> dfs=[&](int u)
{
dfn[u]=++ind;vis[u]=1;
for(auto v:G[u])
{
if(p[u]==v)continue;
if(not vis[v])
{
p[v]=u;
dfs(v);
}
else if(vis[v]==1)
{
cyc++;
if(cyc<=2)
{
int x=u;
cnt[x]++;
while(x!=v)
{
x=p[x];
cnt[x]++;
}
}
}
}
vis[u]=2;
};
dfs(1);
vector<int> tmp,tmp2;
for(int i=1;i<=n;i++)
{
if(cnt[i]==2)
{
tmp2.push_back(i);
}
}
sort(tmp2.begin(),tmp2.end(),[&](int u,int v){return dfn[u]<dfn[v];});
if(tmp2.size()==1u)tmp.push_back(tmp2[0]);
else if(tmp2.size()>=2u)tmp.push_back(tmp2.front()),tmp.push_back(tmp2.back());
vector<int> ans;
auto check=[&](int d)
{
vector<int> pa(n+5);
function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
for(auto [u,v]:edges)
{
if(u==d or v==d)
continue;
int pu=find(u),pv=find(v);
if(pu==pv)return false;
pa[pv]=pu;
}
return true;
};
for(auto x:tmp)if(check(x))ans.push_back(x);
cout<<ans.size()<<endl;
for(auto z:ans)
{
cout<<z<<' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3436kb
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: 0ms
memory: 3436kb
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: 3516kb
input:
3 2 1 3 2 3
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3476kb
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: 3508kb
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: 0ms
memory: 3516kb
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: 3504kb
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: 3460kb
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: 3440kb
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: 3452kb
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: 3500kb
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: 3480kb
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: 3644kb
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: 3540kb
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: -100
Wrong Answer
time: 1ms
memory: 3580kb
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 666 472
result:
wrong answer 2nd numbers differ - expected: '472', found: '666'