Submission #1109859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109859		ozner77	Parachute rings (IOI12_rings)	C++17	0 / 100	707 ms	43848 KiB

rings

#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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31