Submission #997834

#	Time	Username	Problem	Language	Result	Execution time	Memory
997834		biank	Split the Attractions (IOI19_split)	C++14	33 / 100	529 ms	1048576 KiB

split

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())

const int MAX_N = 1e5;

vector<int> adj[MAX_N];

void dfs(int u, vector<int> &vis, int &b, int color, int p = -1) {
    if (!b) return;
    vis[u] = color;
    b--;
    for (int v : adj[u]) if (v != p) {
        if (vis[v] != color) dfs(v, vis, b, color, u);
    }
}

int sz[MAX_N], par[MAX_N];

int getSize(int u, int p = -1) {
    par[u] = p, sz[u] = 1;
    for (int v : adj[u]) if (v != p) {
        sz[u] += getSize(v, u);
    }
    return sz[u];
    
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int color[3] = {1, 2, 3};
    if (a > b) {
        swap(a, b);
        swap(color[0], color[1]);
    }
    if (a > c) {
        swap(a, c);
        swap(color[0], color[3]);
    }
    if (b > c) {
        swap(b, c);
        swap(color[1], color[2]);
    }
    for (int i = 0; i < sz(p); i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    vector<int> ans(n, color[2]);
    if (a == 1) {
        dfs(0, ans, b, color[1]);
        for (int i = 0; i < n; i++) {
            if (ans[i] == color[2]) {
                ans[i] = color[0];
                break;
            }
        }
        return ans;
    }
    getSize(0);
    int u = 0;
    for (int i = 1; i < n; i++) {
        if (sz[i] >= a && sz[i] < sz[u]) u = i;
    }
    if (n - sz[u] < a) return vector<int>(n, 0);
    if (sz[u] < n - sz[u]) {
        dfs(u, ans, a, color[0], par[u]);
        dfs(par[u], ans, b, color[1], u);
    } else {
        dfs(u, ans, b, color[1], par[u]);
        dfs(par[u], ans, a, color[0], u);
    }
    return ans;
}

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