QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44619#996. 割点CCPSDCGK#WA 2ms5644kbC++232.3kb2022-08-20 13:12:282022-08-20 13:12:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-20 13:12:29]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5644kb
  • [2022-08-20 13:12:28]
  • 提交

answer

#include<map>
#include<set>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<random>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
using ll=long long;
using uint=unsigned int;
using ull=unsigned long long;
#define endl '\n'
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define fs fflush(stdout)
#define ump unordered_map
#define pq priority_queue
#define clz __builtin_clz
#define ctz __builtin_ctz
#define sz(x) (int)x.size()
#define np next_permutation
#define clzl __builtin_clzll
#define ctzl __builtin_ctzll
#define ppc __builtin_popcount
#define all(x) x.begin(),x.end()
#define ppcl __builtin_popcountll
#define fpi(x) freopen(x,"r",stdin)
#define fpo(x) freopen(x,"w",stdout)
#define uid uniform_int_distribution
#define urd uniform_real_distribution
#define me(x,y) memset(x,y,sizeof(x))
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<'='<<(x)<<'\n'
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,iosiz,stdin),p1==p2)?EOF:*p1++
#define iosiz 1024
char buf[iosiz],*p1=buf,*p2=buf;
template<class T> inline T &re(T &x){
	x=0;int f=1;char ch=gc;
	while(ch<48||ch>57){
		if(ch==45) f=-f;ch=gc;
	}
	while(ch>47&&ch<58) x=(x<<1)+(x<<3)+(ch^48),ch=gc;
	return x*=f;
}
#define mod 998244353
#define inf 0x3f3f3f3f
int ans,dep,dfn[20005],low[20005],tim;
bool cut[20005],vis[20005];
struct node{
    int to,num;
};
vector<node> edge[20005];
void dfs(int u){
    dfn[u]=low[u]=++tim,dep++;
    int cnt=0;
    for(auto v:edge[u]) if(!vis[v.num]){
        vis[v.num]=1;
        if(!dfn[v.to]){
            dfs(v.to),low[u]=min(low[u],low[v.to]);
            cut[u]|=dep^1&&low[v.to]>=dfn[u],cnt++;
        }
        else low[u]=min(low[u],dfn[v.to]);
    }
    cut[u]|=dep--==1&&cnt>1;
}
int main(){
    #ifdef CCPSDCGK
    fpi("shuju.txt");
    #endif
    int n=re(n),m=re(m);
    for(int i=1;i<=m;i++){
        int u=re(u),v=re(v);
        edge[u].eb((node){v,i}),edge[v].eb((node){u,i});
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
    for(int i=1;i<=n;i++) ans+=cut[i];
    cout<<ans<<endl;
    for(int i=1;i<=n;i++) if(cut[i]) cout<<i<<' ';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 5644kb

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:

3178
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:

wrong answer 1st numbers differ - expected: '1440', found: '3178'