oj.uz

Submission #590956

# Submission time Handle Problem Language Result Execution time Memory
590956 2022-07-06T15:55:14 Z Deepesson Parachute rings (IOI12_rings) C++17
37 / 100
 1497 ms 167616 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;
    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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 20 ms 26456 KB Output is correct
3 Correct 17 ms 26568 KB Output is correct
4 Correct 15 ms 26172 KB Output is correct
5 Correct 16 ms 26544 KB Output is correct
6 Correct 18 ms 26948 KB Output is correct
7 Correct 17 ms 26468 KB Output is correct
8 Correct 17 ms 26580 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26560 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 53316 KB Output is correct
2 Correct 918 ms 94664 KB Output is correct
3 Correct 1338 ms 98116 KB Output is correct
4 Correct 1065 ms 127236 KB Output is correct
5 Correct 1029 ms 131236 KB Output is correct
6 Correct 1497 ms 167616 KB Output is correct
7 Correct 1266 ms 97588 KB Output is correct
8 Correct 1065 ms 116468 KB Output is correct
9 Correct 1109 ms 124724 KB Output is correct
10 Correct 1405 ms 133196 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 20 ms 26456 KB Output is correct
3 Correct 17 ms 26568 KB Output is correct
4 Correct 15 ms 26172 KB Output is correct
5 Correct 16 ms 26544 KB Output is correct
6 Correct 18 ms 26948 KB Output is correct
7 Correct 17 ms 26468 KB Output is correct
8 Correct 17 ms 26580 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26560 KB Output is correct
11 Correct 18 ms 26708 KB Output is correct
12 Correct 20 ms 27108 KB Output is correct
13 Correct 21 ms 27092 KB Output is correct
14 Incorrect 20 ms 26860 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 20 ms 26456 KB Output is correct
3 Correct 17 ms 26568 KB Output is correct
4 Correct 15 ms 26172 KB Output is correct
5 Correct 16 ms 26544 KB Output is correct
6 Correct 18 ms 26948 KB Output is correct
7 Correct 17 ms 26468 KB Output is correct
8 Correct 17 ms 26580 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26560 KB Output is correct
11 Correct 18 ms 26708 KB Output is correct
12 Correct 20 ms 27108 KB Output is correct
13 Correct 21 ms 27092 KB Output is correct
14 Incorrect 20 ms 26860 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 20 ms 26456 KB Output is correct
3 Correct 17 ms 26568 KB Output is correct
4 Correct 15 ms 26172 KB Output is correct
5 Correct 16 ms 26544 KB Output is correct
6 Correct 18 ms 26948 KB Output is correct
7 Correct 17 ms 26468 KB Output is correct
8 Correct 17 ms 26580 KB Output is correct
9 Correct 16 ms 26580 KB Output is correct
10 Correct 17 ms 26560 KB Output is correct
11 Correct 347 ms 53316 KB Output is correct
12 Correct 918 ms 94664 KB Output is correct
13 Correct 1338 ms 98116 KB Output is correct
14 Correct 1065 ms 127236 KB Output is correct
15 Correct 1029 ms 131236 KB Output is correct
16 Correct 1497 ms 167616 KB Output is correct
17 Correct 1266 ms 97588 KB Output is correct
18 Correct 1065 ms 116468 KB Output is correct
19 Correct 1109 ms 124724 KB Output is correct
20 Correct 1405 ms 133196 KB Output is correct
21 Correct 18 ms 26708 KB Output is correct
22 Correct 20 ms 27108 KB Output is correct
23 Correct 21 ms 27092 KB Output is correct
24 Incorrect 20 ms 26860 KB Output isn't correct
25 Halted 0 ms 0 KB -