Submission #1150117

#TimeUsernameProblemLanguageResultExecution timeMemory
1150117enzyParachute rings (IOI12_rings)C++20
0 / 100
350 ms59512 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n, resp, qtd3, viz[maxn], pai[maxn], ciclo, qm, qm3, best, idbest, 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){ 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(na!=qm) ciclo++; sou[na]++; qm=na; } if(na!=nb) merge(na,nb); // se não forem conexos, ligar eles // vendo se a ou o b são o cara de maior grau if(v[a].size()>best){ best=v[a].size(); idbest=find(a); } if(v[b].size()>best){ best=v[b].size(); idbest=find(b); } 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){ qm3=find(a); qtd3++; viz[a]++; int at=0; if(qtd3==viz[a]&&(ciclo&&sou[find(a)])||(!ciclo)) at++; for(int i : v[a]){ viz[i]++; if(viz[i]==qtd3&&(ciclo&&sou[find(i)])||(!ciclo)) at++; } resp=at; } if(v[b].size()==3){ qtd3++; viz[b]++; int at=0; if(qtd3==viz[b]&&(ciclo&&sou[find(b)])||(!ciclo)) at++; for(int i : v[b]){ viz[i]++; 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...