Submission #997836

#	Time	Username	Problem	Language	Result	Execution time	Memory
997836		biank	Split the Attractions (IOI19_split)	C++14	33 / 100	49 ms	15660 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> s, vector<int> e) {
    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]);
    }
    int m = sz(e);
    for (int i = 0; i < m; i++) {
        adj[s[i]].push_back(e[i]);
        adj[e[i]].push_back(s[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;
    }
    if (m == n - 1) {
        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;
    }
    int u = 0, p = -1;
    while (b > 0) {
        if (a > 0) {
            ans[u] = color[0];
            a--;
        } else {
            ans[u] = color[1];
            b--;
        }
        for (int v : adj[u]) {
            if (v != p) {
                p = u;
                u = v;
                break;
            }
        }
    }
    return ans;
}

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