Submission #699207

#	Time	Username	Problem	Language	Result	Execution time	Memory
699207		Cross_Ratio	Parachute rings (IOI12_rings)	C++17	0 / 100	1263 ms	231772 KiB

rings

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