제출 #411818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411818		timmyfeng	Split the Attractions (IOI19_split)	C++17	0 / 100	76 ms	25260 KiB

split

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

const int N = 100001;

int sub[N], dsu[N], color[N];
vector<int> adj[N], span[N];
bool special[N];

int find(int u) {
    if (dsu[u] < 0) {
        return u;
    } else {
        dsu[u] = find(dsu[u]);
        return dsu[u];
    }
}

bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) {
        if (-dsu[u] > -dsu[v]) {
            swap(u, v);
        }
        dsu[v] += dsu[u];
        dsu[u] = v;
        return true;
    }
    return false;
}

void dfs_span(int u) {
    for (auto c : adj[u]) {
        if (adj[c].empty()) {
            span[u].push_back(c);
            span[c].push_back(u);
            dfs_span(c);
        }
    }
}

void dfs_sub(int u, int p = -1) {
    sub[u] = 1;
    for (auto c : span[u]) {
        if (c != p) {
            dfs_sub(c, u);
            sub[u] += sub[c];
        }
    }
}

int dfs_find(int u, int n, int p = -1) {
    for (auto c : span[u]) {
        if (c != p && sub[c] > n / 2) {
            return dfs_find(c, n, u);
        }
    }
    return u;
}

void dfs_unite(int u, int p = -1) {
    for (auto c : span[u]) {
        if (c != p) {
            unite(u, c);
            dfs_unite(c, u);
        }
    }
}

void dfs_color(int u, int x, int &y) {
    color[u] = x;
    --y;

    for (auto c : adj[u]) {
        if (special[c] == special[u] && color[c] == 0 && y > 0) {
            dfs_color(c, x, y);
        }
    }
}

bool visited[N];

int dfs_count(int u) {
    visited[u] = true;
    int ans = 1;
    for (auto c : adj[u]) {
        if (special[c] == special[u] && !visited[c]) {
            ans += dfs_count(c);
        }
    }
    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    fill(adj, adj + n, vector<int>());
    for (int i = 0; i < (int) p.size(); ++i) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }

    fill(span, span + n, vector<int>());
    dfs_span(0);

    dfs_sub(0);
    int root = dfs_find(0, n);

    fill(dsu, dsu + n, -1);
    for (auto u : span[root]) {
        dfs_unite(u, root);
    }

    int ans = -1;
    for (int i = 0; i < n; ++i) {
        if (i != root && -dsu[find(i)] >= min({a, b, c})) {
            ans = find(i);
        }
    }

    for (int i = 0; i < n && ans == -1; ++i) {
        for (auto j : adj[i]) {
            if (i != root && j != root && unite(i, j)) {
                if (-dsu[find(i)] >= min({a, b, c})) {
                    ans = find(i);
                    break;
                }
            }
        }
    }

    if (ans == -1) {
        return vector<int>(n);
    }

    for (int i = 0; i < n; ++i) {
        special[i] = find(i) == ans;
    }

    int x_min, x_mid;
    if (a <= min(b, c)) {
        x_min = 1;
        x_mid = b <= c ? 2 : 3;
    } else if (b <= min(a, c)) {
        x_min = 2;
        x_mid = a <= c ? 1 : 3;
    } else {
        x_min = 3;
        x_mid = a <= b ? 1 : 2;
    }

    int y_min = vector<int>{a, b, c}[x_min - 1];
    int y_mid = vector<int>{a, b, c}[x_mid - 1];

    fill(color, color + n, 0);
    dfs_color(-dsu[ans] <= n / 2 ? ans : root, x_min, y_min);
    dfs_color(-dsu[ans] <= n / 2 ? root : ans, x_mid, y_mid);

    fill(visited, visited + n, false);
    assert(dfs_count(ans) + dfs_count(root) == n);

    for (int i = 0; i < n; ++i) {
        if (color[i] == 0) {
            color[i] = x_min ^ x_mid;
        }
    }

    return vector<int>(color, color + n);
}

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