Submission #1150121

#TimeUsernameProblemLanguageResultExecution timeMemory
1150121enzyParachute rings (IOI12_rings)C++20
0 / 100
403 ms59096 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n, resp, qtd3, viz[maxn], pai[maxn], ciclo, sou[maxn], qtd4; vector<int>v[maxn]; 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_){ resp = n = N_; for(int i=0;i<n;i++) pai[i]=i; } void Link(int a, int b){ if(qtd4>=2||ciclo>=2){ resp=0; return; } v[a].push_back(b); v[b].push_back(a); int na=find(a), nb=find(b); if(na==nb){ // são um ciclo if(!sou[na]){ // precisa retirar tds os caras q n fazem parte do ciclo da resp ciclo++; resp=0; for(int i=0;i<n;i++){ if((ciclo&&sou[find(i)])||(!ciclo)){ // se tem ciclo precisamos quebrá-lo if(qtd3){ // precisamos garantir tbm q n tem caras com grau maior q 3 if(viz[i]==qtd3) resp++; // tiro td uma aresta de td mundo q tem grau maior ou igual a 3 }else resp++; } } } sou[na]++; } if(na!=nb) merge(na,nb); // se não forem conexos, ligar eles if(v[a].size()==4) qtd4++; if(v[b].size()==4) qtd4++; if(qtd4>=2||ciclo>=2){ resp=0; return; } if(v[a].size()>=4){ if(qtd3==viz[a]&&(ciclo&&sou[find(a)])||(!ciclo)) resp=1; // checando se quebra ciclo e se tira td mundo com grau grande return; } if(v[b].size()>=4){ // mesma coisa do a if(qtd3==viz[b]&&(ciclo&&sou[find(b)])||(!ciclo)) resp=1; return; } // agr sabemos q tem apenas caras com grau 3 ou menos e há no máximo um ciclo if(v[a].size()==3){ qtd3++; viz[a]++; // aumentando a qtd int at=0; if(qtd3==viz[a]&&(ciclo&&sou[find(a)])||(!ciclo)) at++; // checa se o a está no ciclo e tira tds os extras for(int i : v[a]){ viz[i]++; // aumentando a qtd if(viz[i]==qtd3&&(ciclo&&sou[find(i)])||(!ciclo)) at++; // checa se o i está no ciclo e tira tds os extras } resp=at; } if(v[b].size()==3){ qtd3++; viz[b]++; // aumentando a qtd int at=0; if(qtd3==viz[b]&&(ciclo&&sou[find(b)])||(!ciclo)) at++; for(int i : v[b]){ viz[i]++; // aumentando a qtd if(viz[i]==qtd3&&(ciclo&&sou[find(i)])||(!ciclo)) at++; } resp=at; } } int CountCritical(){ 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...