oj.uz

Submission #699206

# Submission time Handle Problem Language Result Execution time Memory
699206 2023-02-16T05:50:27 Z Cross_Ratio Parachute rings (IOI12_rings) C++14
0 / 100
 1265 ms 231808 KB 
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> root;
    vector<int> deg;
    int cypt = -1;
    bool deg3 = false;
    void init(int N) {
        root.resize(N);
        deg.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        deg[x]++, deg[y]++;
        if(deg[x]>=3) deg3 = true;
        if(deg[y]>=3) deg3 = true;
        x = Find(x), y = Find(y);
        if(x==y) {
            if(cypt==-1) cypt = x;
            else cypt = -2;
            return;
        }
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int N;
int cnt;
array<int, 2> Edge[1000005];
vector<int> adj[1000005];
set<int> S;
int deg[1000005];
UnionFind U;
UnionFind UF[4];
int id[1000005];
int id2[5];
bool idcnt = false;
void Init(int _N) {
    N = _N;
    int i;
    for(i=0;i<N;i++) S.insert(i);
    if(S.size() <= 4 && !idcnt) {
        idcnt = true;
        int ck = 0;
        for(int n : S) {
            id[n] = ck;
            ck++;
        }
    }
    U.init(N);
    for(i=0;i<4;i++) UF[i].init(N);
}
void Link(int x, int y) {
    deg[x]++, deg[y]++;
    adj[x].push_back(y);
    adj[y].push_back(x);
    if(deg[x] == 3) {
        set<int> S2;
        S2.insert(x);
        for(int n : adj[x]) S2.insert(n);
        for(int n : S2) {
            if(S.find(n) == S.end()) S2.erase(n);
        }
        S = S2;
    }
    if(deg[x] >= 4) {
        if(S.find(x) == S.end()) S = set<int> {};
        else S = set<int>{x};
    }
    if(deg[y] == 3) {
        set<int> S2;
        S2.insert(y);
        for(int n : adj[y]) S2.insert(n);
        for(int n : S2) {
            if(S.find(n) == S.end()) S2.erase(n);
        }
        S = S2;
    }
    if(deg[y] >= 4) {
        if(S.find(y) == S.end()) S = set<int> {};
        else S = set<int>{y};
    }
    if(S.size() <= 4 && !idcnt) {
        idcnt = true;
        int ck = 0;
        for(int n : S) {
            id[n] = ck;
            id2[ck] = n;
            for(int i = 0; i < cnt; i++) {
                if(Edge[i][0] != n && Edge[i][1] != n) {
                    UF[ck].Merge(Edge[i][0], Edge[i][1]);
                }
            }
            ck++;
        }
    }
    U.Merge(x, y);
    if(idcnt) {
        for(int i=0;i<4;i++) {
            if(x != id2[i] && y != id2[i]) {
                UF[i].Merge(x, y);
            }
        }
    }
    Edge[cnt++] = {x, y};
}
int CountCritical() {
    if(S.size() == 0) return 0;
    if(!idcnt) {
        //assert(!U.deg3);
        if(U.cypt==-1) return N;
        else if(U.cypt==-2) return 0;
        else return -U.root[U.Find(U.cypt)];
    }
    else {
        int cnt = 0;
        for(int n : S) {
            if(!UF[id[n]].deg3 && UF[id[n]].cypt == -1) cnt++;
        }
        return cnt;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 16 ms 24408 KB Output is correct
4 Correct 14 ms 23856 KB Output is correct
5 Correct 12 ms 24140 KB Output is correct
6 Correct 14 ms 24504 KB Output is correct
7 Runtime error 33 ms 49004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 90948 KB Output is correct
2 Correct 1265 ms 116188 KB Output is correct
3 Runtime error 400 ms 231808 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 16 ms 24408 KB Output is correct
4 Correct 14 ms 23856 KB Output is correct
5 Correct 12 ms 24140 KB Output is correct
6 Correct 14 ms 24504 KB Output is correct
7 Runtime error 33 ms 49004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 16 ms 24408 KB Output is correct
4 Correct 14 ms 23856 KB Output is correct
5 Correct 12 ms 24140 KB Output is correct
6 Correct 14 ms 24504 KB Output is correct
7 Runtime error 33 ms 49004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct
3 Correct 16 ms 24408 KB Output is correct
4 Correct 14 ms 23856 KB Output is correct
5 Correct 12 ms 24140 KB Output is correct
6 Correct 14 ms 24504 KB Output is correct
7 Runtime error 33 ms 49004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -