| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1150118 | enzy | Parachute rings (IOI12_rings) | C++20 | 0 ms | 0 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(na!=qm){
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(t[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;
}