Submission #382363

#	Time	Username	Problem	Language	Result	Execution time	Memory
382363		ParsaAlizadeh	Parachute rings (IOI12_rings)	C++17	100 / 100	1349 ms	87892 KiB

rings

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

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
//#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 1e6 + 10;

int n, mark[N], par[N], sz[N], ans = -1, vgt2;
vector<int> adj[N];
vector<pii> E;

struct TmpDSU {
    int flag = true, u, par[N];

    TmpDSU() {
        fill(par, par + N, -1);
    }

    int find(int u) {
        return (this->par[u] == -1 ? u : this->par[u] = find(this->par[u]));
    }

    void merge(int u, int v) {
        if (!flag || u == this->u || v == this->u)
            return;
        u = find(u), v = find(v);
        if (u == v) {
            flag = false;
            return;
        }
        if (v < u) swap(u, v);
        this->par[v] = u;
    }
} tmpdsu[4];

int dsufind(int u) {
    return (par[u] == -1 ? u : par[u] = dsufind(par[u]));
}

void dsumerge(int u, int v) {
    u = dsufind(u), v = dsufind(v);
    if (u == v) {
        if (!vgt2)
            ans = (ans != -1 ? 0 : sz[u]);
        return;
    }
    if (sz[v] > sz[u])
        swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

void apply(int u) {
    if (adj[u].size() <= 2)
        return;
    if (vgt2) {
        for (int i = 0; i < 4; i++) {
            bool f = tmpdsu[i].u == u;
            if (adj[u].size() == 3)
            for (int v : adj[u])
                f |= tmpdsu[i].u == v;
            tmpdsu[i].flag &= f;
        }
        return;
    }
    vgt2 = 1;
    assert(adj[u].size() == 3);
    tmpdsu[0].u = u;
    for (int i = 0; i < 3; i++)
        tmpdsu[i + 1].u = adj[u][i];
    for (auto &e : E) {
        for (int i = 0; i < 4; i++) 
            tmpdsu[i].merge(e.X, e.Y);
    }
}

void Init(int N_) {
    n = N_;
    fill(par, par + n, -1);
    fill(sz, sz + n, 1);
}

void Link(int u, int v) {
    E.emplace_back(u, v);
    adj[u].push_back(v);
    adj[v].push_back(u);

    if (vgt2)
    for (int i = 0; i < 4; i++) {
        tmpdsu[i].merge(u, v);
    }

    dsumerge(u, v);
    apply(u);
    apply(v);
}

int CountCritical() {
    if (!vgt2)
        return (ans == -1 ? n : ans);
    int t = 0;
    for (int i = 0; i < 4; i++)
        t += tmpdsu[i].flag;
    return t;
}

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