Submission #1226958

#TimeUsernameProblemLanguageResultExecution timeMemory
1226958FaggiParachute rings (IOI12_rings)C++20
0 / 100
944 ms327680 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define forn(i,n) for(i=0; i<n; i++) #define all(x) x.begin(),x.end() #define pb push_back #define mp make_pair #define fr first #define se second using namespace std; const int MAXN=1e6+1; map<ll,bool>m[MAXN]; vector<ll>grafo[MAXN]; ll n, tim, vis[MAXN], id[MAXN], ars, nods; void Init(int N) { n=N; } bool dfs(ll nod, ll pad, ll prob) { vis[nod]=tim; for(auto k:grafo[nod]) { if(k==pad||k==prob||vis[k]==tim+1) continue; if(vis[k]==tim) return 1; if(dfs(k,nod,prob)) return 1; } vis[nod]=tim+1; return 0; } void dfs2(ll nod, ll pad) { nods++; vis[nod]=tim; for(auto k:grafo[nod]) { ars++; if(k==pad&&vis[nod]>=tim) continue; dfs2(k,nod); } vis[nod]=tim+1; } int CountCritical() { vector<ll>cant3(n,0); ll res=0, ban, i, j, cant=0; ll cuat=0, pos; for(i=0; i<n; i++) { if(id[i]>=4) { cuat++; pos=i; } else if(id[i]==3) { for(auto k:grafo[i]) cant3[k]++; cant3[i]++; cant++; } } if(cuat>1) return 0; tim=0; memset(vis,0,sizeof(vis)); if(cuat==1) { tim+=2; ban=0; i=pos; for(j=0; j<n; j++) { if(j==i) continue; if(vis[j]==tim+1) continue; if(dfs(j,0,i)) ban=1; } if(cant3[pos]==cant&&ban==0) res++; } else { tim+=2; ll mal=0, dif=0; vector<pair<ll,ll>>subs; for(i=0; i<n; i++) { if(vis[i]!=tim+1) { nods=0; ars=0; dfs2(i,-1); ars/=2; subs.pb({nods,ars}); if(ars>=nods) { mal++; dif=abs((nods-1)-ars); } } } if(mal==0) return n; if(mal>1) return 0; for(i=0; i<n; i++) { tim+=2; ban=0; for(j=0; j<n; j++) { if(j==i) continue; if(vis[j]==tim+1) continue; if(dfs(j,0,i)) ban=1; } if(ban==0&&cant3[i]==cant) res++; } } return res; } void Link(int a, int b) { if(m[a][b]==1) return; m[a][b]=1; m[b][a]=1; grafo[a].pb(b); grafo[b].pb(a); id[a]++; id[b]++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...