Submission #1215898

#TimeUsernameProblemLanguageResultExecution timeMemory
1215898moondarksideParachute rings (IOI12_rings)C++20
0 / 100
4096 ms60356 KiB
#include <iostream> #include<bits/stdc++.h> using namespace std; bool Sense=false; bool four=false; 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>(); } 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); } void pLink(int A,int B,int N) { vector<vector<int>> tmp=TreeCritId; vector<int> tmp2=CritId; Connections[A].push_back(B); if(Connections[A].size()<3) { return; } if(Connections[A].size()<3 && CritId.size()==0) { return; } if(Connections[A].size()==3 && CritId.size()==0) { CritId.push_back(A); for(int i=0; i<3; i++) { CritId.push_back(Connections[A][i]); } 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); } 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; } if(Connections[A].size()==3) { Connections[A].push_back(B); 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; } } Connections[A].push_back(B); return; } void Link(int A, int B) { pLink(A,B,Connections.size()); pLink(B,A,Connections.size()); vector<vector<int>> tmp=TreeCritId; vector<int> tmp2=CritId; 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]); } } } tmp=TreeCritId; tmp2=CritId; } 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...