Submission #1177298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177298		DippleThree	Parachute rings (IOI12_rings)	C++20	0 / 100	717 ms	113840 KiB

rings

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct union_find{
    int size, num_components;
    vector<int> sz, dad;
    union_find(){}
    union_find(int n){
        size = n; num_components = n;
        sz.resize(n);
        dad.resize(n);
        for (int i = 0; i < n; i++){
            sz[i] = 1;
            dad[i] = i;
        }
    }
    int find(int x){
        if (dad[x] == x) return x;
        return dad[x] = find(dad[x]);
    }
    bool unite(int x, int y){ // returns true if already connected
        x = find(x);
        y = find(y);
        if (x == y) return true;
        if (sz[x] < sz[y]){
            dad[x] = y;
            sz[y] += sz[x];
        } else {
            dad[y] = x;
            sz[x] += sz[y];
        }
        num_components--;
        return false;
    }
};

union_find uf(1);
vector<int> deg;
int mx_deg = 0;
int n;
vector<vector<int>> conns;
bool has_cyc = false;
set<int> pos{};

int ans;

map<int, pair<pair<bool, union_find>, pair<vector<int>, int>>> mp; // pos -> [has_cyc, uf], [degs, mx_deg]

void Init(int N){
    n = N;
    ans = n;
    uf = union_find(n);
    deg.resize(n);
    conns.resize(n);
    for (int i = 0; i < n; i++){
        pos.insert(i);
    }
}
void Link(int a, int b){
    deg[a]++;
    mx_deg = max(mx_deg, deg[a]);
    deg[b]++;
    mx_deg = max(mx_deg, deg[b]);
    conns[a].push_back(b);
    conns[b].push_back(a);
    if (mx_deg <= 1){
        uf.unite(a, b);
    } if (mx_deg == 2){
        if (uf.unite(a, b)){
            if (has_cyc){
                ans = 0;
                pos = set<int>();
                return;
            } else {
                int fnd = uf.find(a);
                for (int i = 0; i < n; i++){
                    if (uf.find(i) == fnd){
                        pos.insert(i);
                    }
                }
                ans = pos.size();
                has_cyc = true;
            }
        }
    } else if (mx_deg == 3){
        if (deg[a] == 3){
            set<int> pos2{};
            if (pos.count(a)){
                pos2.insert(a);
            }
            for (int i : conns[a]){
                if (pos.count(i)){
                    pos2.insert(i);
                }
            }
            pos = pos2;
        }
        if (deg[b] == 3){
            set<int> pos2{};
            if (pos.count(b)){
                pos2.insert(b);
            }
            for (int i : conns[b]){
                if (pos.count(i)){
                    pos2.insert(i);
                }
            }
            pos = pos2;
        }
        uf.unite(a, b);
    } else {
        if (deg[a] == 3){
            set<int> pos2{};
            if (pos.count(a)){
                pos2.insert(a);
            }
            for (int i : conns[a]){
                if (pos.count(i)){
                    pos2.insert(i);
                }
            }
            pos = pos2;
        } else if (deg[a] > 3){
            if (pos.count(a)){
                pos = {a};
            } else {
                pos = {};
            }
        }
        if (deg[b] == 3){
            set<int> pos2{};
            if (pos.count(b)){
                pos2.insert(b);
            }
            for (int i : conns[b]){
                if (pos.count(i)){
                    pos2.insert(i);
                }
            }
            pos = pos2;
        } else if (deg[b] > 3){
            if (pos.count(b)){
                pos = {b};
            } else {
                pos = {};
            }
        }
        uf.unite(a, b);
    }
    if (mx_deg >= 3){
        ans = 0;
        for (int x : pos){
            if (!mp.count(x)){
                mp[x] = {{false, union_find(n)}, {vector<int>(n), 0}};
                for (int i = 0; i < n; i++){
                    if (i == x) continue;
                    for (int j : conns[i]){
                        if (j == x) continue;
                        if (j > i) continue;
                        mp[x].second.first[i]++;
                        mp[x].second.second = max(mp[x].second.second, mp[x].second.first[i]);
                        mp[x].second.first[j]++;
                        mp[x].second.second = max(mp[x].second.second, mp[x].second.first[j]);
                        if (mp[x].first.second.unite(i, j)){
                            mp[x].first.first = true;
                        }
                    }
                }
            } else {
                if (a == x || b == x){
                    if (!mp[x].first.first && mp[x].second.second <= 2) ans++;
                    continue;
                }
                mp[x].second.first[a]++;
                mp[x].second.second = max(mp[x].second.second, mp[x].second.first[a]);
                mp[x].second.first[b]++;
                mp[x].second.second = max(mp[x].second.second, mp[x].second.first[b]);
                if (mp[x].first.second.unite(a, b)){
                    mp[x].first.first = true;
                }
            }
            if (!mp[x].first.first && mp[x].second.second <= 2) ans++;
        }
    }
}
int CountCritical(){
    return ans;
}

#ifdef LOCAL
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    Init(7);
    cout << CountCritical() << "\n";
    Link(0, 1);
    cout << CountCritical() << "\n";
    Link(0, 2);
    cout << CountCritical() << "\n";
    Link(1, 2);
    cout << CountCritical() << "\n";
    Link(3, 1);
    cout << CountCritical() << "\n";
    Link(3, 2);
    cout << CountCritical() << "\n";
    Link(1, 4);
    cout << CountCritical() << "\n";
    Link(3, 4);
    cout << CountCritical() << "\n";
}
#endif

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31