Submission #1215907

#TimeUsernameProblemLanguageResultExecution timeMemory
1215907moondarksideParachute rings (IOI12_rings)C++20
0 / 100
427 ms66764 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; void Init(int N) { Connections=std::vector<vector<int>>(N); CritId=vector<int>(); } //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) { for(int i=0; i<4; i++) { bool Valid=false; if(CritId[i]==A) { Valid=true; } for(int j=0; j<3; j++) { if(CritId[i]==Connections[A][j]) { Valid=true; } } if(!Valid) { CritId[i]=-1; } } return; } for(int i=0;i<4;i++){ if(CritId[i]!=A) { CritId[i]=-1; } } return; } void Link(int A, int B) { pLink(A,B,Connections.size()); pLink(B,A,Connections.size()); if(CritId.size()==0){ Fixes.push_back({A,B}); return; } 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() { if(CritId.size()==0){ return Connections.size(); } 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...