Submission #1111540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111540		vjudge1	Parachute rings (IOI12_rings)	C++14	100 / 100	675 ms	105332 KiB

rings

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REV(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define ll long long
#define fi first
#define se second

using namespace std;

const int N = 1e6 + 5;

int n, dsu[N], deg[N], c, sz[N], cy, res;
vector<int> g[N];
vector<pair<int, int>> edge;

int root(int u) {
    if(u == dsu[u]) return u;
    return dsu[u] = root(dsu[u]);
}
struct DSU {
    int rt, fa[N], ans, deg[N];
    int root(int u) {
        if(u == fa[u]) return u;
        return fa[u] = root(fa[u]);
    }
    bool join(int u, int v) {
        if(u == rt || v == rt || ans == 0) return false;
        if(++deg[u] == 3) ans = 0;
        if(++deg[v] == 3) ans = 0;
        u = root(u), v = root(v);
        if(u == v) {
            ans = 0;
            return false;
        }
        fa[u] = v;
        return true;
    }
    void init() {
        ans = 1;
        REP(i, n) fa[i] = i;
        for(auto x : edge) join(x.fi, x.se);
    }
} ds[4];
int q;

void Init(int _n) {
    n = _n;
    REP(i, n) {
        dsu[i] = i, sz[i] = 1;
    }
}
void Link(int u, int v) {
    if(c) REP(i, 4) ds[i].join(u, v);
    else {
        edge.emplace_back(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        if(deg[u] + 1 == 3 || deg[v] + 1 == 3) c = 1;
        if(++deg[u] == 3) {
            ds[0].rt = u;
            REP(i, 3) ds[i + 1].rt = g[u][i];
            REP(i, 4) ds[i].init();
            return;
        }
        if(++deg[v] == 3) {
            ds[0].rt = v;
            REP(i, 3) ds[i + 1].rt = g[v][i];
            REP(i, 4) ds[i].init();
            return;
        }
        if(root(u) != root(v)) {
            u = root(u); v = root(v);
            sz[u] += sz[v];
            dsu[v] = u;
        } else {
            res = sz[root(u)];
            ++cy;
        }
    }
}
int CountCritical() {
    if(cy > 1) return 0;
            else if(c) return ds[0].ans + ds[1].ans + ds[2].ans + ds[3].ans;
            else if(cy == 1) return res;
            return n;
}

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