Submission #1021432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021432		vjudge1	Split the Attractions (IOI19_split)	C++17	22 / 100	604 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

const ll MAXN = 1E5+16;
vll adj[MAXN];
ll sz[MAXN];
vll ord1, ord2;

void dfs_1 (ll u, ll par) {
    sz[u] = 1;
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_1(v, u);
        sz[u] += sz[v];
    }
}

void dfs_2 (ll u, ll par, ll blk, bool underBlk) {
    underBlk |= u == blk;
    (underBlk?ord1:ord2).push_back(u);
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_2(v, u, blk, underBlk);
    }
}

vi find_split (int n, int aaa, int bbb, int ccc, vi us, vi vs) {
    pair <ll, ll> pa = { aaa, 1 }, pb = { bbb, 2 }, pc = { ccc, 3 };
    if (pa > pb) swap(pa, pb);
    if (pb > pc) swap(pb, pc);
    if (pa > pb) swap(pa, pb);
    ll a = pa.first, b = pb.first, c = pc.first;
    // assert(a <= b && b <= c);
    ll m = us.size();
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back(vs[i]);
        adj[vs[i]].push_back(us[i]);
    }
    dfs_1(0, 0);
    ll blk1 = -16, blk2 = -16;
    for (ll u = 0; u < n; u++) {
        if (sz[u]>=a && n-sz[u]>=b) blk1 = u;
        if (sz[u]>=b && n-sz[u]>=a) blk2 = u;
    }
    if (blk1 != -16) {
        dfs_2(0, 0, blk1, false);
        // for (ll i : ord1) cerr << i << ' ';
        // cerr << '\n';
        // for (ll i : ord2) cerr << i << ' ';
        // cerr << '\n';
        vi ans(n, pc.second);
        for (ll i = 0; i < a; i++) ans[ord1[i]] = pa.second;
        for (ll i = 0; i < b; i++) ans[ord2[i]] = pb.second;
        return ans;
    }
    if (blk2 != -16) {
        dfs_2(0, 0, blk2, false);
        // for (ll i : ord1) cerr << i << ' ';
        // cerr << '\n';
        // for (ll i : ord2) cerr << i << ' ';
        // cerr << '\n';
        vi ans(n, pc.second);
        for (ll i = 0; i < b; i++) ans[ord1[i]] = pb.second;
        for (ll i = 0; i < a; i++) ans[ord2[i]] = pa.second;
        return ans;
    }
    return vi(n, 0);
}

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:36:36: warning: unused variable 'c' [-Wunused-variable]
   36 |     ll a = pa.first, b = pb.first, c = pc.first;
      |                                    ^

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