Submission #1150116

#TimeUsernameProblemLanguageResultExecution timeMemory
1150116enzyParachute rings (IOI12_rings)C++20
37 / 100
376 ms64716 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n, pai[maxn], ciclo, sou[maxn], qtd4, id4, add[maxn], t[maxn]; vector<int>v[maxn], grnd; bool ja=false; void merge(int a, int b){ pai[b]=a; } int find(int a){ if(pai[a]==a) return a; return pai[a]=find(pai[a]); } void Init(int N_){ n = N_; for(int i=0;i<n;i++) pai[i]=i; } void Link(int a, int b){ v[a].push_back(b); v[b].push_back(a); int na=find(a), nb=find(b); if(na==nb){ if(!sou[na]) ciclo++; sou[na]++; } if(na!=nb) merge(na,nb); if(v[a].size()==3){ grnd.push_back(a); for(int viz : v[a]) t[viz]++; t[a]++; } if(v[b].size()==3){ grnd.push_back(b); for(int viz : v[b]) t[viz]++; t[b]++; } if(v[a].size()==4){ qtd4++; id4=a;} if(v[b].size()==4){ qtd4++; id4=b;} } int CountCritical(){ int resp=0; if(qtd4>=2||ciclo>=2) return 0; if(qtd4){ // se tem um cara com grau maior ou igual a 4, necessariamente precisamos retirá-lo if((ciclo&&sou[find(id4)])||(!ciclo)){ // se tem ciclo precisamos quebrá-lo if(grnd.size()){ // precisamos garantir tbm q n tem caras com grau maior q 3 if(t[id4]==grnd.size()) resp++; // tiro td uma aresta de td mundo q tem grau maior ou igual a 3 }else resp++; } return resp; } // agora temos apenas um ou menos ciclos e tds tem grau menor ou igual a 3 for(int i=0;i<n;i++){ if((ciclo&&sou[find(i)])||(!ciclo)){ // se tem ciclo precisamos quebrá-lo if(grnd.size()){ // precisamos garantir tbm q n tem caras com grau maior q 3 if(t[i]==grnd.size()) resp++; // tiro td uma aresta de td mundo q tem grau maior ou igual a 3 }else resp++; } } 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...