Submission #1111726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111726		vjudge1	Parachute rings (IOI12_rings)	C++17	17 / 100	770 ms	119408 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>

#define fi first
#define se second

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 = 0;
        par.resize(nmax + 1);
        deg.resize(nmax + 1);
        for (int i = 1; i <= nmax; i++) {
            par[i] = i;
            deg[i] = 0;
        }
    }

    void init() {
        ans = 1;
        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) ans = 0;
        if (++deg[v] == 3) ans = 0;

        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 = 1; 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] == 2 || deg[v] == 2) check = true;

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

    if (++deg[v] == 3) {
        ds[0].root = v;
        for (int i = 1; i < 4; i++) ds[i].root = adj[v][i - 1];
        for (int i = 0; i < 4; i++) ds[i].init();
        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;
}

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