Submission #544967

#	Time	Username	Problem	Language	Result	Execution time	Memory
544967		tabr	Parachute rings (IOI12_rings)	C++17	100 / 100	1685 ms	116296 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

int n;
int mx;
vector<vector<int>> g;
vector<int> deg;
dsu uf = 1;

struct info {
    int ignore;
    int ok;
    vector<int> ideg;
    dsu iuf = 1;

    info(int ignore_) {
        ignore = ignore_;
        ok = 1;
        ideg = vector<int>(n);
        iuf = dsu(n);
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                if (i == ignore || j == ignore || i > j) {
                    continue;
                }
                if (!iuf.unite(i, j)) {
                    ok = 0;
                }
                ideg[i]++;
                ideg[j]++;
            }
        }
        if (*max_element(ideg.begin(), ideg.end()) > 2) {
            ok = 0;
        }
    }

    void add(int x, int y) {
        if (x == ignore || y == ignore || ok == 0) {
            return;
        }
        ideg[x]++;
        ideg[y]++;
        if (max(ideg[x], ideg[y]) > 2) {
            ok = 0;
            return;
        }
        if (!iuf.unite(x, y)) {
            ok = 0;
            return;
        }
    }
};

vector<info> cands;
vector<int> loops;

void Init(int n_) {
    n = n_;
    g = vector<vector<int>>(n);
    deg = vector<int>(n);
    uf = dsu(n);
}

void Link(int x, int y) {
    g[x].emplace_back(y);
    g[y].emplace_back(x);
    deg[x]++;
    deg[y]++;
    bool t = uf.unite(x, y);
    int new_mx = max({mx, deg[x], deg[y]});
    if (new_mx == 3 && mx == 2) {
        if (deg[x] == 3) {
            cands.emplace_back(info(x));
        } else {
            cands.emplace_back(info(y));
        }
        for (int z : g[cands[0].ignore]) {
            cands.emplace_back(info(z));
        }
    } else if (mx <= 2) {
        if (!t) {
            loops.emplace_back(uf.get(x));
        }
    } else {
        for (int i = 0; i < 4; i++) {
            cands[i].add(x, y);
        }
    }
    swap(mx, new_mx);
}

int CountCritical() {
    int ans = 0;
    if (mx >= 3) {
        for (int i = 0; i < 4; i++) {
            ans += cands[i].ok;
        }
    } else {
        if (loops.size() == 0) {
            ans = n;
        } else if (loops.size() == 1) {
            ans = uf.size(loops[0]);
        }
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Init(7);
    cout << CountCritical() << endl;  // 7
    Link(1, 2);
    cout << CountCritical() << endl;  // 7
    Link(0, 5);
    cout << CountCritical() << endl;  // 7
    Link(2, 0);
    cout << CountCritical() << endl;  // 7
    Link(3, 2);
    cout << CountCritical() << endl;  // 4
    Link(3, 5);
    cout << CountCritical() << endl;  // 3
    Link(4, 3);
    cout << CountCritical() << endl;  // 2
    return 0;
}
#endif

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