QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31977#996. 割点gsh#WA 3ms5060kbC++23874b2022-05-14 15:09:162022-05-14 15:09:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-14 15:09:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5060kb
  • [2022-05-14 15:09:16]
  • 提交

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'