Submission #590956

#	Time	Username	Problem	Language	Result	Execution time	Memory
590956		Deepesson	Parachute rings (IOI12_rings)	C++17	37 / 100	1497 ms	167616 KiB

rings

#include <bits/stdc++.h>
///Entendi o problema incorretamente
#define MAX 1100000
int N;
std::vector<int> candidatos;
std::vector<int> con[MAX];

int pai[MAX];

int find(int a){
    if(pai[a]==a)
        return a;
    return pai[a]=find(pai[a]);
}

void Union(int a,int b){
    a=find(a);
    b=find(b);
    pai[a]=b;
}

void Init(int N_) {

    N = N_;
    for(int i=0;i!=N;++i)candidatos.push_back(i);
    for(int i=0;i!=N;++i)pai[i]=i;
}

///Nao pode ter ciclo, eh isso
void Prunar(int x){
    if(con[x].size()==3){
        std::map<int,bool> pode;
        pode[x]=true;
        for(auto&z:con[x])pode[z]=true;
        std::vector<int> novcad;
        for(auto&z:candidatos){
            if(pode[z])novcad.push_back(z);
        }
        candidatos=novcad;
    }else if(con[x].size()==4){
        std::vector<int> novcad;
        for(auto&z:candidatos){
            if(z==x)novcad.push_back(z);
        }
        candidatos=novcad;
    }
}

int visitou[MAX];
std::map<int,bool> podendo;
int obj;
bool explora(int pos,int prev){
    if(visitou[pos])return false;
    if(pos==obj){
        return true;
    }
    for(auto&x:con[pos]){
        if(x==prev)continue;
        if(explora(x,pos)){
            podendo[pos]=1;
            return true;
        }
    }
    return false;
}

void PrunaConjunto(int x){
    std::queue<int> queue;
    queue.push(x);
    while(queue.size()){
        auto __ = queue.front();
        queue.pop();
        if(visitou[__])continue;
        visitou[__]=true;
        for(auto&x:con[__])queue.push(x);
    }
}

void Explorar(int A,int B){
    podendo.clear();
    obj=B;
    podendo[A]=1;
    podendo[B]=1;
    explora(A,-1);
    PrunaConjunto(A);
    PrunaConjunto(B);
    std::vector<int> novcad;
    for(auto&z:candidatos){
        if(podendo[z])novcad.push_back(z);
    }
    candidatos=novcad;
}


void Link(int A, int B) {
    con[A].push_back(B);
    con[B].push_back(A);

    if(find(A)==find(B)){
        Explorar(A,B);
    }
    Union(A,B);

    Prunar(A);
    Prunar(B);
}

int CountCritical() {
  return candidatos.size();
}

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