Submission #1226948

#TimeUsernameProblemLanguageResultExecution timeMemory
1226948FaggiParachute rings (IOI12_rings)C++20
20 / 100
4098 ms167868 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; ll cuat=0, pos, cant2=0; 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)); for(i=0; i<n; i++) { tim+=2; ban=0; for(j=0; j<n; j++) { if(j==i) continue; cant=0; for(auto k:grafo[j]) { if(k==i) continue; cant++; } if(cant>2) ban=1; if(vis[j]==tim+1) continue; if(dfs(j,0,i)) ban=1; } if(ban==0) 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...