Submission #1021268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021268		vjudge1	Split the Attractions (IOI19_split)	C++17	0 / 100	682 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;
bool vis[MAXN];
vll adj[MAXN];
ll sz[MAXN];
ll par[MAXN];
vll ord2, ord3;

void dfs_1 (ll u, ll par) {
    ::par[u] = 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) {
    if (u == blk) return;
    ord2.push_back(u);
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_2(v, u, blk);
    }
}

void dfs_3 (ll u, ll par) {
    ord3.push_back(u);
    for (ll v : adj[u]) {
        if (v == par) continue;
        dfs_3(v, u);
    }
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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;
    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]);
    }
    ll src = rng()%n;
    src = 0;
    dfs_1(src, src);
    ll blk = -15;
    for (ll u = 0; u < n; u++) {
        if (sz[u] < a) continue;
        if (n-sz[u] < b) continue;
        blk = u;
    }
    if (blk == -15) return vi(n, 0);
    dfs_2(src, src, blk);
    dfs_3(blk, par[blk]);
    vi ans(n, pc.second);
    for (ll i = 0; i < a; i++) ans[ord3[i]] = pa.second;
    for (ll i = 0; i < b; i++) ans[ord2[i]] = pb.second;
    return ans;
}

Compilation message (stderr)

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

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