Submission #1215928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215928		moondarkside	Parachute rings (IOI12_rings)	C++20	100 / 100	540 ms	84284 KiB

rings

#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;
bool inposible=false;;

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) {
    if(inposible){
        return ;
    }
    //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)){
            if(b!=-1){
                inposible=true;
            }
            int k=getRoot(B,Treec);
            b=0;
			for(int i=0;i<Treec.size();i++){
			    if(getRoot(i,Treec)==k){
			        b++;
			    }
			}
			
		}
        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(inposible){
        return 0;
    }
    if(b!=-1 & CritId.size()==0){
        return b;
    }
    
    if(CritId.size()==0){
        return Connections.size();
    }
    
    int v=0;
    for(int i=0;i<4;i++){
        if(CritId[i]!=-1){
            v++;
        }
    }
    if(v==0){
        inposible=true;
    }
    return v;
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31