Submission #699209

#	Time	Username	Problem	Language	Result	Execution time	Memory
699209		Cross_Ratio	Parachute rings (IOI12_rings)	C++14	52 / 100	4054 ms	166264 KiB

rings

#include <bits/stdc++.h>
using namespace std;
set<array<int, 2>> S2;
vector<vector<int>> adj;
struct UnionFind {
    vector<int> root;
    int cypt = -1;
    bool deg3 = false;
    int pt = -1;
    void init(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    void bye() {
        root.clear();
        root.shrink_to_fit();
    }
    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) {
        if(deg3) return;
        int d1 = adj[x].size() - (S2.find({min(pt, x), max(pt, x)})!=S2.end()?1:0);
        int d2 = adj[y].size() - (S2.find({min(pt, y), max(pt, y)})!=S2.end()?1:0);
        if(d1>=3) deg3 = true;
        if(d2>=3) deg3 = true;
        if(deg3) bye();
        if(deg3) return;
        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;
set<int> S;
UnionFind U;
UnionFind UF[4];
map<int, int> id;
int id2[5];
bool idcnt = false;
void Init(int _N) {
    N = _N;
    adj.resize(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;
            UF[ck].pt = n;
            id2[ck] = n;
            ck++;
            UF[ck].init(N);
        }
    }
    else U.init(N);
}
void Link(int x, int y) {
    adj[x].push_back(y);
    adj[y].push_back(x);
    S2.insert({min(x, y), max(x, y)});
    if(adj[x].size() == 3) {
        set<int> S2;
        S2.insert(x);
        for(int n : adj[x]) S2.insert(n);
        vector<int> v;
        for(int n : S) {
            if(S2.find(n) == S2.end()) v.push_back(n);
        }
        for(int n : v) S.erase(n);
    }
    if(adj[x].size() >= 4) {
        if(S.find(x) == S.end()) S = set<int> {};
        else S = set<int>{x};
    }
    if(adj[y].size() == 3) {
        set<int> S2;
        S2.insert(y);
        for(int n : adj[y]) S2.insert(n);
        vector<int> v;
        for(int n : S) {
            if(S2.find(n) == S2.end()) v.push_back(n);
        }
        for(int n : v) S.erase(n);
    }
    if(adj[y].size() >= 4) {
        if(S.find(y) == S.end()) S = set<int> {};
        else S = set<int>{y};
    }
    bool now = false;
    if(S.size() <= 4 && !idcnt) {
        idcnt = true;
        now = true;
        int ck = 0;
        U.bye();
        for(int n : S) {
            id[n] = ck;
            id2[ck] = n;
            UF[ck].pt = n;
            UF[ck].init(N);
            for(auto k : S2) {
                if(k[0] != n && k[1] != n) {
                    UF[ck].Merge(k[0], k[1]);
                }
            }
            ck++;
        }
    }
    if(!idcnt) U.Merge(x, y);
    if(idcnt && !now) {
        for(int i=0;i<4;i++) {
            if(x != id2[i] && y != id2[i]) {
                UF[i].Merge(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: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 0 / 31