Submission #1108123

#TimeUsernameProblemLanguageResultExecution timeMemory
1108123GabrielParachute rings (IOI12_rings)C++17
55 / 100
4062 ms107292 KiB
#include "bits/stdc++.h" using namespace std; long long n; vector< vector<long long> > Grafo; vector<long long> Visitados; void Init(int N_) { n = (long long)N_; Grafo.assign(n, vector<long long>()); } void Link(int A, int B){ long long a = (long long)A; long long b = (long long)B; Grafo[a].push_back(b); Grafo[b].push_back(a); } int Bien; long long Ciclos; void DFS(long long Nodo, long long Anterior){ Visitados[Nodo] = 1; long long c = 0; for(auto E: Grafo[Nodo]){ if(Visitados[E] == 1) c++; if(Visitados[E] == 1 and E != Anterior){ Bien = 0; } if(Visitados[E] == 0){ DFS(E, Nodo); c++; } } if(c >= 3){ Bien = 0; } } int CountCritical(){ int r = 0; vector<long long> Buenos; for(long long i = 0; i < n; i++){ if(Grafo[i].size() >= 4){ Bien = 1; Visitados.assign(n, 0); Visitados[i] = 2; for(long long j = 0; j < n; j++){ if(i == j) continue; if(Visitados[j] == 0){ DFS(j, -2); } } return Bien; } } bool Solo_4 = 0; for(long long i = 0; i < n; i++){ if(Grafo[i].size() == 3){ Buenos.push_back(i); for(auto E: Grafo[i]){ Buenos.push_back(E); } Solo_4 = 1; break; } } if(Solo_4){ for(auto i: Buenos){ Bien = 1; Visitados.assign(n, 0); Visitados[i] = 2; for(long long j = 0; j < n; j++){ if(i == j) continue; if(Visitados[j] == 0){ DFS(j, -2); } } r += Bien; } } else { Ciclos = 0; Visitados.assign(n, 0); long long Ciclado; for(long long i = 0; i < n; i++){ if(!Visitados[i]){ Bien = 1; DFS(i, -2); if(Bien == 0) Bien = 1; else Bien = 0; Ciclos += Bien; if(Bien == 1) Ciclado = i; } } if(Ciclos > 1) return 0; else if(Ciclos == 1){ set<long long> Tenemos; while(1){ if(Tenemos.find(Ciclado) != Tenemos.end()) break; r++; Tenemos.insert(Ciclado); long long a = Grafo[Ciclado][0], b = Grafo[Ciclado][1]; if(Tenemos.count(a) == 0) Ciclado = a; else Ciclado = b; } } else { return (int)n; } } return r; }
#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...