Submission #1193378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193378		dong_gas	Split the Attractions (IOI19_split)	C++20	18 / 100	66 ms	15432 KiB

split

#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int MAXN = 1e5 + 10;
int n, m, a, b, c, can = -1;
int sz[MAXN], visited[MAXN], papa[MAXN];
vector<int> res, adj[MAXN];

void dfs(int u, int p = -1) {
    sz[u] = visited[u] = 1;
    papa[u] = p;
    for (int& v: adj[u]) {
        if (visited[v]) continue;
        dfs(v, u), sz[u] += sz[v];
    }
    if (sz[u] >= a && n - sz[u] >= b) can = u;
}

void go(int u) {
    visited[u] = 1;
    if (a == 0) return;
    if (a-- > 0) res[u] = 1;
    else return;
    for (int& v: adj[u]) {
        if (v == papa[can] || visited[v]) continue;
        go(v);
    }
}

void gogo(int u) {
    // cout << u << endl;
    visited[u] = 1;
    if (b == 0) return;

    if (b-- > 0) res[u] = 2;
    else return;

    for (int& v: adj[u]) {
        if (visited[v]) continue;
        gogo(v);
    }
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
    vector<pair<int, int>> v = {{_a, 1}, {_b, 2}, {_c, 3}};
    memset(visited, 0, sizeof(visited));
    sort(all(v));
    a = v[0].first, b = v[1].first, c = v[2].first, n = _n, m = p.size(), can = -1;
    // cout << a << ' ' << b << ' ' << c << endl;
    for (int i = 0; i < m; i++) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
    dfs(0);
    if (can == -1) return vector<int>(n, 0);
    res.resize(n, 3);

    memset(visited, 0, sizeof(visited));
    // cout << can << ' ' << papa[can] << endl;
    go(can), gogo(papa[can]);

    // for (int i = 0; i < n; i++) cout << i << ": " << v[res[i] - 1].second << '\n';
    for (int i = 0; i < n; i++) res[i] = v[res[i] - 1].second, adj[i].clear();
    return res;
}

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