QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44619 | #996. 割点 | CCPSDCGK# | WA | 2ms | 5644kb | C++23 | 2.3kb | 2022-08-20 13:12:28 | 2022-08-20 13:12:29 |
Judging History
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'