Submission #535838

#	Time	Username	Problem	Language	Result	Execution time	Memory
535838		KoD	Split the Attractions (IOI19_split)	C++17	100 / 100	182 ms	25680 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, forward<Args>(args)...);
    }
};

struct union_find {
    vector<int> par;
    explicit union_find(const int n) : par(n, -1) {}
    int find(const int u) { 
        return par[u] < 0 ? u : par[u] = find(par[u]); 
    }
    int size(const int u) {
        return -par[find(u)];
    }
    bool same(const int x, const int y) { 
        return find(x) == find(y); 
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
};

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    const array<int, 3> size = {a, b, c};
    a = 0, b = 1, c = 2;
    if (size[a] > size[b]) swap(a, b);
    if (size[b] > size[c]) swap(b, c);
    if (size[a] > size[b]) swap(a, b);
    const int m = (int)p.size();
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; ++i) {
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
    }
    vector<vector<int>> tree(n);
    vector<char> done(n);
    vector<int> subtree(n);
    rec_lambda([&](auto&& dfs, const int u) -> void {
        done[u] = true;
        subtree[u] = 1;
        for (const int v : graph[u]) {
            if (!done[v]) {
                tree[u].push_back(v);
                tree[v].push_back(u);
                dfs(v);
                subtree[u] += subtree[v];
            }
        }
    })(0);
    int g = 0;
    for (int p = -1;;) {
        bool f = false;
        for (const int u : tree[g]) {
            if (u != p and subtree[u] * 2 > n) {
                p = g;
                g = u;
                f = true;
                break;
            }
        }
        if (!f) break;
    }
    union_find dsu(n);
    int found = -1;
    for (const int u : tree[g]) {
        rec_lambda([&](auto&& dfs, const int u, const int p) -> void {
            for (const int v : tree[u]) {
                if (v != p) {
                    dsu.merge(u, v);
                    dfs(v, u);
                }
            }
        })(u, g);
        if (dsu.size(u) >= size[a]) found = u;
    }
    for (int i = 0; i < m; ++i) {
        if (found != -1) break;
        if (p[i] == g or q[i] == g) continue;
        dsu.merge(p[i], q[i]);
        if (dsu.size(p[i]) >= size[a]) found = p[i];
        if (dsu.size(q[i]) >= size[a]) found = q[i];
    }
    vector<int> result(n);
    if (found == -1) return result;
    int count = size[a];
    rec_lambda([&](auto&& dfs, const int u) -> void {
        if (result[u] != 0 or !dsu.same(found, u) or count == 0) return;
        result[u] = a + 1;
        count -= 1;
        for (const int v : graph[u]) dfs(v);
    })(found);
    count = size[b];
    rec_lambda([&](auto&& dfs, const int u) -> void {
        if (result[u] != 0 or count == 0) return;
        result[u] = b + 1;
        count -= 1;
        for (const int v : graph[u]) dfs(v);
    })(g);
    for (auto& x : result) {
        if (x == 0) x = c + 1;
    }
    return result;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36