Submission #286511

#	Time	Username	Problem	Language	Result	Execution time	Memory
286511		PeppaPig	Parachute rings (IOI12_rings)	C++14	0 / 100	1314 ms	123476 KiB

rings

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e6 + 5;

struct UnionFind {
    bool bad = false;
    int cyc_sz = 0, cyc_cnt = 0, cand = -1, all;
    int par[N], end[N], sz[N], cyc[N];

    UnionFind() {}

    void reset() {
        iota(par, par + N, 0);
        iota(end, end + N, 0);
        fill_n(sz, N, 1);
    }

    int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

    void add_edge(int a, int b) {
        if(bad || a == cand || b == cand) return;
        if(cyc[find(a)] || cyc[find(b)]) {
            bad = true;
            return;
        }
        if(find(a) == find(b)) {
            if(cyc[find(a)]) bad = true;
            else {
                cyc[find(a)] = 1;
                cyc_sz += sz[find(a)];
                ++cyc_cnt;
                if(cyc_cnt > 1) bad = true;
            }
            return;
        }
        if((a != find(a) && a != end[find(a)]) || (b != find(b) && b != end[find(b)])) {
            bad = true;
            return;
        }
        if(a == find(a) && b == find(b)) {
            par[a] = end[a], par[end[a]] = end[a];
            par[b] = find(a), end[find(a)] = end[b], sz[find(a)] += sz[b];
        } else if(a == end[find(a)] && b == end[find(b)])
            end[find(b)] = find(a), par[find(a)] = find(b), sz[find(b)] += sz[find(a)];
        else if(a == find(a) && b == end[find(b)])
            par[a] = find(b), end[find(b)] = end[a], sz[find(b)] += sz[a];
        else if(a == end[find(a)] && b == find(b))
            par[b] = find(a), end[find(a)] = end[b], sz[find(a)] += sz[b];
    }

    int count() {
        if(bad) return 0;
        if(cyc_cnt) return cyc_sz;
        return all;
    }
} dsu[4];

int n;
bool found;
vector<pii> E;
vector<int> g[N];

void Init(int _n) {
    n = _n;
    for(int i = 0; i < 4; i++) {
        dsu[i].reset();
        dsu[i].all = n;
    }
}

void Link(int a, int b) {
    E.emplace_back(a, b);
    g[a].emplace_back(b), g[b].emplace_back(a);
    if(!found) {
        if((int)g[a].size() < 3 && (int)g[b].size() < 3)
            dsu[0].add_edge(a, b);
        else {
            found = true;
            int candid = (int)g[a].size() == 3 ? a : b;
            vector<int> ret = {candid};
            for(int v : g[candid]) ret.emplace_back(v);
            for(int i = 0; i < 4; i++) {
                dsu[i].reset();
                dsu[i].cand = ret[i];
            }
            for(pii e : E) for(int i = 0; i < 4; i++)
                dsu[i].add_edge(e.x, e.y);
        }
    } else for(int i = 0; i < 4; i++)
        dsu[i].add_edge(a, b);
}

int CountCritical() {
    if(found) {
        int ans = 0;
        for(int i = 0; i < 4; i++) if(dsu[i].count() && !dsu[i].cyc_cnt)
            ++ans;
        return ans;
    } else return dsu[0].count();
}

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