QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31977 | #996. 割点 | gsh# | WA | 3ms | 5060kb | C++23 | 874b | 2022-05-14 15:09:16 | 2022-05-14 15:09:18 |
Judging History
answer
#include<algorithm>
#include<iostream>
#include<random>
#include<vector>
#include<cstdio>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define MAXN 20001
int N,M,tot,dfn[MAXN],low[MAXN];vector<int>E[MAXN];bool ans[MAXN];
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
void dfs(int u,bool isrt){dfn[u]=low[u]=++tot;int c=0;for(auto v:E[u]){if(!dfn[v]){dfs(v,0),low[u]=min(low[u],low[v]),c++;if(!isrt&&low[v]>=dfn[u])ans[u]=1;}low[u]=min(low[u],low[v]);}if(isrt&&c>1)ans[u]=1;}
int main()
{
N=get(),M=get();For(i,1,M){int u=get(),v=get();E[u].push_back(v),E[v].push_back(u);}
For(i,1,N)if(!dfn[i])dfs(i,1);int c=0;For(i,1,N)c+=ans[i];cout<<c<<'\n';For(i,1,N)if(ans[i])cout<<i<<' ';cout<<'\n';return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 5060kb
input:
12783 21968 4933 7832 8238 2739 3628 7841 9169 6390 7850 8797 8120 8710 5306 9807 10166 2063 2666 5157 5015 4651 4790 12586 10366 7137 12440 7218 6330 3670 2735 8492 1968 2750 6237 1112 6578 9221 743 3820 7155 4583 2537 9747 11331 9916 4454 5631 2978 10340 5293 1803 4944 4296 11800 2742 7903 2018 10...
output:
393 22 27 39 45 47 62 118 163 183 239 248 285 313 337 347 358 415 513 557 608 626 639 644 647 694 716 779 788 797 798 841 900 908 933 984 1033 1101 1127 1136 1207 1213 1242 1249 1285 1339 1348 1372 1375 1429 1566 1568 1614 1625 1692 1696 1750 1821 1826 1830 1832 1838 1839 1840 1848 1858 1960 2166 21...
result:
wrong answer 1st numbers differ - expected: '1440', found: '393'