Submission #597988

#	Time	Username	Problem	Language	Result	Execution time	Memory
597988		Johann	Split the Attractions (IOI19_split)	C++14	40 / 100	108 ms	24140 KiB

split

// sub1-3
#include "bits/stdc++.h"

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef long long ll;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 100100;
int A = 0, B = 0, C = 0;
int va = 1, vb = 2, vc = 3;
int size[MAXN] = {0};

void dfs(vvi &adj, int v, vvi &tre) {
    size[v] = 1;
    for (int u: adj[v]) {
        if (size[u] == 0) {
            tre[v].push_back(u);
            tre[u].push_back(v);
            dfs(adj, u, tre);
            size[v] += size[u];
        }
    }
}

void fillSub(vvi &tre, int v, int p, int value, vi &ans) {
    if ((value == va && A == 0) || (value == vb && B == 0)) return;
    ans[v] = value;
    if (value == va) --A;
    else --B;
    for (int u : tre[v]) {
        if (u == p) continue;
        fillSub(tre, u, v, value, ans);
    }
}

vi find_split(int n, int a, int b, int c, vi p, vi q) {
    if (a > b) swap(a, b), swap(va, vb);
    if (a > c) swap(a, c), swap(va, vc);
    if (b > c) swap(b, c), swap(vb, vc);
    A = a, B = b, C = c;
    vvi adj(n);
    for (int i = 0; i < sz(p); ++i) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
    vvi tre(n);
    int root = 0;
    dfs(adj, root, tre);
    vi ans(n, root);
    while (true) {
        vpii children;
        for (int u: adj[root]) children.push_back({size[u], u});
        sort(all(children));
        reverse(all(children));
        int submax = children.front().second;
        if (size[submax] < a) return ans;
        else if (size[submax] > n - a) {
            // move the root
            size[root] = n - size[submax];
            size[submax] = n;
            root = submax;
        } else {
            ans.assign(n, vc);
            // construct solution:
            if (size[submax] >= b) {
                swap(va, vb);
                swap(A, B);
            }
            // subtree filled
            fillSub(tre, submax, root, va, ans);
            // fill rest
            fillSub(tre, root, submax, vb, ans);
            return ans;
        }
    }
}

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