Submission #1215924

#TimeUsernameProblemLanguageResultExecution timeMemory
1215924moondarksideParachute rings (IOI12_rings)C++20
0 / 100
428 ms70712 KiB
#include <iostream> #include<bits/stdc++.h> using namespace std; std::vector<vector<int>> Connections; vector<int> CritId; vector<vector<int>> TreeCritId; vector<pair<int,int>> Fixes; vector<int> Treec; int b=1; void Init(int N) { Connections=std::vector<vector<int>>(N); CritId=vector<int>(); for(int i=0; i<N; i++) { Treec.push_back(i); } } //Union Find int getRoot(int A,vector<int>& Tree) { if(Tree[A]==A) { return A; } int pos=getRoot(Tree[A],Tree); Tree[A]=pos; return pos; } void join(int A,int B,vector<int>& Tree) { Tree[getRoot(A,Tree)]=getRoot(B,Tree); } //Unir void pLink(int A,int B,int N) { Connections[A].push_back(B); //No hay problema if(Connections[A].size()<3) { return; } //Básico if(Connections[A].size()==3 && CritId.size()==0) { //Init CritId.push_back(A); for(int i=0; i<3; i++) { CritId.push_back(Connections[A][i]); } //UF init vector<int>Tree; for(int i=0; i<N; i++) { Tree.push_back(i); } for(int i=0; i<4; i++) { TreeCritId.push_back(Tree); } //UF join for(int j=0; j<Fixes.size(); j++) { int tA=Fixes[j].first; int tB=Fixes[j].second; for(int i=0; i<4; i++) { if(CritId[i]!=-1 && CritId[i]!=tA && CritId[i]!=tB) { if(getRoot(tA,TreeCritId[i])==getRoot(tB,TreeCritId[i])) { CritId[i]=-1; } else { join(tA,tB,TreeCritId[i]); } } } } return; } //Básico if(Connections[A].size()==3) { //Comprobar V3 juntos for(int i=0; i<4; i++) { //Inicio No bool Valid=false; //El vértice es si mismo if(CritId[i]==A) { Valid=true; } //Está en contacto for(int j=0; j<3; j++) { if(CritId[i]==Connections[A][j]) { Valid=true; } } //Descartar if(!Valid) { CritId[i]=-1; } } return; } //En caso gV>3 //Descartar todo excepto A for(int i=0;i<4;i++){ if(CritId[i]!=A) { CritId[i]=-1; } } return; } void Link(int A, int B) { //En ambos vértices pLink(A,B,Connections.size()); pLink(B,A,Connections.size()); //Mantener para el futuro. if(CritId.size()==0){ Fixes.push_back({A,B}); if(getRoot(A,Treec)==getRoot(B,Treec)){ b+=-1; } join(A,B,Treec); return; } //UF joint for(int i=0; i<4; i++) { if(CritId[i]!=-1 && CritId[i]!=A && CritId[i]!=B) { if(getRoot(A,TreeCritId[i])==getRoot(B,TreeCritId[i])){ CritId[i]=-1; } else { join(A,B,TreeCritId[i]); } } } } int CountCritical() { //Si no hay v2+ if(CritId.size()==0){ return Connections.size()+min(b,0); } int v=0; for(int i=0;i<4;i++){ if(CritId[i]!=-1){ v++; } } return v; }
#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...