oj.uz

Submission #590962

# Submission time Handle Problem Language Result Execution time Memory
590962 2022-07-06T16:00:08 Z Deepesson Parachute rings (IOI12_rings) C++17
37 / 100
 1511 ms 154728 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 16 ms 26484 KB Output is correct
3 Correct 16 ms 26432 KB Output is correct
4 Correct 14 ms 26196 KB Output is correct
5 Correct 17 ms 26528 KB Output is correct
6 Correct 17 ms 26836 KB Output is correct
7 Correct 15 ms 26360 KB Output is correct
8 Correct 16 ms 26572 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26580 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 46432 KB Output is correct
2 Correct 860 ms 83972 KB Output is correct
3 Correct 1295 ms 85348 KB Output is correct
4 Correct 1085 ms 113900 KB Output is correct
5 Correct 1048 ms 117740 KB Output is correct
6 Correct 1511 ms 154728 KB Output is correct
7 Correct 1274 ms 85348 KB Output is correct
8 Correct 1018 ms 103644 KB Output is correct
9 Correct 1105 ms 111392 KB Output is correct
10 Correct 1357 ms 120500 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 16 ms 26484 KB Output is correct
3 Correct 16 ms 26432 KB Output is correct
4 Correct 14 ms 26196 KB Output is correct
5 Correct 17 ms 26528 KB Output is correct
6 Correct 17 ms 26836 KB Output is correct
7 Correct 15 ms 26360 KB Output is correct
8 Correct 16 ms 26572 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26580 KB Output is correct
11 Incorrect 17 ms 26580 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 16 ms 26484 KB Output is correct
3 Correct 16 ms 26432 KB Output is correct
4 Correct 14 ms 26196 KB Output is correct
5 Correct 17 ms 26528 KB Output is correct
6 Correct 17 ms 26836 KB Output is correct
7 Correct 15 ms 26360 KB Output is correct
8 Correct 16 ms 26572 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26580 KB Output is correct
11 Incorrect 17 ms 26580 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 16 ms 26484 KB Output is correct
3 Correct 16 ms 26432 KB Output is correct
4 Correct 14 ms 26196 KB Output is correct
5 Correct 17 ms 26528 KB Output is correct
6 Correct 17 ms 26836 KB Output is correct
7 Correct 15 ms 26360 KB Output is correct
8 Correct 16 ms 26572 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26580 KB Output is correct
11 Correct 328 ms 46432 KB Output is correct
12 Correct 860 ms 83972 KB Output is correct
13 Correct 1295 ms 85348 KB Output is correct
14 Correct 1085 ms 113900 KB Output is correct
15 Correct 1048 ms 117740 KB Output is correct
16 Correct 1511 ms 154728 KB Output is correct
17 Correct 1274 ms 85348 KB Output is correct
18 Correct 1018 ms 103644 KB Output is correct
19 Correct 1105 ms 111392 KB Output is correct
20 Correct 1357 ms 120500 KB Output is correct
21 Incorrect 17 ms 26580 KB Output isn't correct
22 Halted 0 ms 0 KB -