oj.uz

Submission #1109859

# Submission time Handle Problem Language Result Execution time Memory
1109859 2024-11-07T23:11:18 Z ozner77 Parachute rings (IOI12_rings) C++17
0 / 100
 707 ms 43848 KB 
#include <bits/stdc++.h>
using namespace std;
map<long long,long long> sumas;
    vector<int> p, r;
    void UnionFind(int n) {
        p.resize(n);
        r.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    int encontrar(int x) {
        if (p[x] != x) {
            p[x] = encontrar(p[x]);
        }
        return p[x];
    }
    void unir(int x, int y) {
        int rx = encontrar(x);
        int ry = encontrar(y);
        if (rx != ry) {
            if (r[rx] > r[ry]) {
                p[ry] = rx;
            } else if (r[rx] < r[ry]) {
                p[rx] = ry;
            } else {
                p[ry] = rx;
                r[rx]++;
            }
        }
    }
    bool conectados(int x, int y) {
        return encontrar(x) == encontrar(y);
    }
int N;
void Init(int N){
    UnionFind(N);
}
void Link(int A,int B){
    unir(A,B);
    sumas[A]++;
    sumas[B]++;
}
int CountCritical(){
    int res=0;
    vector<long long> Puntas;
    for(int i=0;i<N;i++){
        Puntas.clear();
        for(int j=0;j<N;j++){
            if(j!=i){
                if(sumas[j]>=3){
                    break;
                }else if(sumas[j]==1){
                    Puntas.push_back(j);
                }
            }
        }
        map<long long,long long> C;
        C.clear();
        bool vale=true;
        for(auto x:Puntas){
            C[encontrar(x)]++;
            if(C[encontrar(x)]>2){
                 vale=false;
                break;
            }
        }
        if(vale){
            res++;
        }
    }
    return res;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 707 ms 43848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -