Submission #1111735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111735		vjudge1	Parachute rings (IOI12_rings)	C++17	100 / 100	799 ms	119496 KiB

rings

#include <bits/stdc++.h>
using namespace std;

#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

#define ll long long
#define pii pair<int, int>

const int nmax = 1e6 + 5;

int theta, n, q;
int u, v, cyc, res;
bool check = false;

int par[nmax], sz[nmax], deg[nmax];
vector<pii> edges;
vector<int> adj[nmax];

struct DSU {
    int root, ans;
    vector<int> par, deg;

    DSU() {
        ans = 1;
        root = -1;
        par.resize(nmax + 1);
        deg.resize(nmax + 1);
        for (int i = 1; i <= nmax; i++) {
            par[i] = i;
            deg[i] = 0;
        }
    }

    void init(int r) {
        ans = 1; root = r;
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            // deg[i] = 0;
        }
        for (auto [u, v] : edges) {
            merge(u, v);
        }
    }

    int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    
    void merge(int u, int v) {
        if (u == root || v == root || ans == 0) return;
        if (++deg[u] == 3 || ++deg[v] == 3) {
            ans = 0;
            return;
        }
        u = find(u), v = find(v);
        if (u == v) {
            ans = 0;
            return;
        }
        par[u] = v;
    }
} ds[4];

int find(int u) {
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void Init(int _n) {
    n = _n;
    for (int i = 0; i <= n; i++) {
        par[i] = i;
        deg[i] = 0;
        sz[i] = 1;
    }
}

void Link(int u, int v) {
    if (check) {
        for (int i = 0; i < 4; i++)
            ds[i].merge(u, v);
        return;
    }
    edges.push_back({u, v});
    adj[u].push_back(v);
    adj[v].push_back(u);
    if (deg[u] + 1 == 3 || deg[v] + 1 == 3) check = true;

    if (++deg[u] == 3) {
        ds[0].init(u);
        for (int i = 1; i < 4; i++) ds[i].init(adj[u][i - 1]);
        return;
    }

    if (++deg[v] == 3) {
        ds[0].init(v);
        for (int i = 1; i < 4; i++) ds[i].init(adj[v][i - 1]);
        return;
    }

    u = find(u), v = find(v);
    if (u == v) {
        res = sz[u];
        cyc++;
    } else {
        sz[u] += sz[v];
        par[v] = u;
    }
}

int CountCritical() {
    if (cyc > 1) return 0;
    if (check) return ds[0].ans + ds[1].ans + ds[2].ans + ds[3].ans;
    if (cyc == 1) return res;
    return n;
}

// int main() {
//     synchronize;
//     // cin >> theta;
//     cin >> n >> q;
//     init(n);
//     for (int i = 1; i <= q; i++) {
//         cin >> u;
//         if (u == -1) {
//             cout << count() << '\n';
//         } else {
//             cin >> v;
//             merge(u, v);
//         }
//     }
// }

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