Submission #1153102

#TimeUsernameProblemLanguageResultExecution timeMemory
1153102enzyParachute rings (IOI12_rings)C++20
0 / 100
4093 ms44212 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; vector<int>v[maxn]; int marc[maxn], n, grau[maxn]; bool ok; void dfs(int u, int vim, int tirei){ marc[u]++; for(int viz : v[u]){ if(viz==vim||viz==tirei) continue; if(marc[viz]){ ok=false; continue; } dfs(viz,u,tirei); } } void Init(int N_){ n = N_; for(int i=0;i<n;i++) v[i].clear(); } void Link(int a, int b){ v[a].push_back(b); v[b].push_back(a); } int CountCritical(){ int resp=0; for(int i=1;i<=n;i++) grau[i]=v[i].size(); for(int i=1;i<=n;i++){ grau[i]=0; // tirando o cara i for(int viz : v[i]) grau[viz]--; // tirando suas arestas bool pd=true; for(int j=1;j<=n;j++){ if(grau[j]>=3) pd=false; // se tiver algm com grau >=3 acabou marc[j]=0; } if(pd){ ok=true; for(int j=1;j<=n;j++) if(!marc[j]&&j!=i) dfs(j,i,i); // fznd a dfs pra ver se encontra ciclo if(ok) resp++; } // recolocando o cara i for(int viz : v[i]) grau[viz]++; grau[i]=v[i].size(); } return resp; }
#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...