oj.uz

Submission #590961

# Submission time Handle Problem Language Result Execution time Memory
590961 2022-07-06T15:59:40 Z Deepesson Parachute rings (IOI12_rings) C++17
0 / 100
 1310 ms 85392 KB 
#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;
    bool u = (!explora(A,-1));
    PrunaConjunto(A);
    PrunaConjunto(B);
    if(!u)return;
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 19 ms 26408 KB Output is correct
3 Correct 18 ms 26436 KB Output is correct
4 Incorrect 15 ms 26196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 46424 KB Output is correct
2 Correct 822 ms 84080 KB Output is correct
3 Correct 1310 ms 85392 KB Output is correct
4 Incorrect 835 ms 66952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 19 ms 26408 KB Output is correct
3 Correct 18 ms 26436 KB Output is correct
4 Incorrect 15 ms 26196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 19 ms 26408 KB Output is correct
3 Correct 18 ms 26436 KB Output is correct
4 Incorrect 15 ms 26196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 19 ms 26408 KB Output is correct
3 Correct 18 ms 26436 KB Output is correct
4 Incorrect 15 ms 26196 KB Output isn't correct
5 Halted 0 ms 0 KB -