Submission #736009

#	Time	Username	Problem	Language	Result	Execution time	Memory
736009		horiseun	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	4059 ms	78900 KiB

rings

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

int n, cycsz;
bool nne;
vector<int> adj[1000005];
vector<pair<int, int>> edges;

struct UnionFind1 {
    int rt, par[1000005], deg[1000005];
    bool vld;

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

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void merge(int x, int y) {
        if (!vld || x == rt || y == rt) return;
        if (deg[x] == 2 || deg[y] == 2 || same(x, y)) {
            vld = false;
            return;
        }
        deg[x]++;
        deg[y]++;
        par[find(x)] = find(y);
    }
    
    UnionFind1(int root) {
        rt = root;
        vld = true;
        for (int i = 0; i < 1000005; i++) {
            par[i] = i;
            deg[i] = 0;
        }
        for (auto [a, b] : edges) {
            merge(a, b);
        }
    }
};

struct UnionFind2 {
    int par[1000005], sz[1000005];
    
    UnionFind2() {
        for (int i = 0; i < 1000005; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

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

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
} cyc;

vector<UnionFind1> uf;

void Init(int N) {
    n = N;
}

int CountCritical() {
    if (nne) return 0;
    if (!uf.empty()) {
        int ans = 0;
        for (UnionFind1 u : uf) {
            ans += u.vld;
        }
        return ans;
    } else if (cycsz) return cycsz;
    return n;
}

void Link(int a, int b) {
    if (nne) return;
    if (!uf.empty()) {
        for (UnionFind1 u : uf) {
            u.merge(a, b);
        }
        return;
    }
    edges.push_back({a, b});
    adj[a].push_back(b);
    adj[b].push_back(a);
    if (adj[a].size() < adj[b].size()) swap(a, b);
    if (adj[a].size() == 3) {
        uf.push_back(UnionFind1(a));
        for (int i : adj[a]) {
            uf.push_back(UnionFind1(i));
        }
        return;
    }
    if (!cyc.merge(a, b)) {
        if (cycsz) {
            nne = true;
            return;
        }
        cycsz = cyc.sz[cyc.find(a)];
    }
}

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