Submission #1150843

#TimeUsernameProblemLanguageResultExecution timeMemory
1150843enzyParachute rings (IOI12_rings)C++20
17 / 100
529 ms121680 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n, qm3, qm4, pai[maxn], ciclo, qtd4, caras[maxn], grau[maxn], tam, tira[maxn], qtd3; vector<int>v[maxn], usar[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_){ n = N_; for(int i=0;i<n;i++) pai[i]=i; } void lenhadora(){ for(int i=1;i<=n;i++){ usar[i]=v[i]; grau[i]=v[i].size(); } queue<int>q; for(int i=1;i<=n;i++) if(grau[i]==1) q.push(i); while(!q.empty()){ int u=q.front(); q.pop(); for(int viz : v[u]){ if(grau[viz]){ grau[viz]--; if(grau[viz]<=1) q.push(viz); } } } for(int i=1;i<=n;i++){ if(grau[i]){ caras[i]++; tam++; } } } 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){ // irão formar um ciclo if(ciclo){ if(caras[a]==0||caras[b]==0) ciclo++; }else{ lenhadora(); ciclo++; } } 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(v[a].size()>=4) qm4=a; if(v[b].size()>=4) qm4=b; // agr sabemos q tem apenas caras com grau 3 ou menos e há no máximo um ciclo if(v[a].size()==3){ qtd3++; tira[a]++; // aumentando a qtd for(int i : v[a]) tira[i]++; // aumentando a qtd qm3=a; } if(v[b].size()==3){ qtd3++; tira[b]++; // aumentando a qtd for(int i : v[b]) tira[i]++; // aumentando a qtd qm3=b; } } int CountCritical(){ if(qtd4>=2||ciclo>=2) return 0; if(qtd4){ if(tira[qm4]==qtd3&&caras[qm4]==ciclo) return 1; else return 0; } if(qtd3){ int resp=0; for(int viz : v[qm3]) if(tira[viz]==qtd3&&caras[viz]==ciclo) resp++; if(tira[qm3]==qtd3&&caras[qm3]==ciclo) resp++; return resp; } if(ciclo) return tam; else return n; }
#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...