Submission #1226952

#TimeUsernameProblemLanguageResultExecution timeMemory
1226952FaggiParachute rings (IOI12_rings)C++20
20 / 100
4100 ms167996 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]; 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; } 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 { 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...