Submission #1229340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229340		Gray	Split the Attractions (IOI19_split)	C++20	22 / 100	555 ms	1114112 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;

vector<vector<int>> A;
vector<ll> sz;   ll n;
bool found=0;

void build(ll u, ll p, vector<int> &vals, ll wr, ll &cnt){
    vals[u]=wr; cnt--;
    if (cnt==0) return;
    for (auto v:A[u]){
        if (v==p) continue;
        build(v, u, vals, wr, cnt);
        if (cnt==0) return;
    }
}

void dfs(ll u, ll p, vector<array<ll, 2>> &cs, vector<int> &vals){
    vector<pair<ll, ll>> szs; ll csz=1;
    for (auto v:A[u]){
        if (v==p) continue;
        dfs(v, u, cs, vals);
        if (found) return;
        csz+=sz[v]; szs.push_back({sz[v], u});
    }
    if (u!=p) szs.push_back({n-csz, p});
    sort(szs.rbegin(), szs.rend());
    for (ll i=0; i<(ll)szs.size(); i++){
        if (szs[i].ff>=cs[1][0] and n-szs[i].ff>=cs[0][0]){
            found=1; vals.assign(n, cs[2][1]);
            build(szs[i].ss, u, vals, cs[1][1], cs[1][0]);
            build(u, szs[i].ss, vals, cs[0][1], cs[0][0]);
            return;
        }
        if (szs[i].ff>=cs[0][0] and n-szs[i].ff>=cs[1][0]){
            found=1; vals.assign(n, cs[2][1]);
            build(szs[i].ss, u, vals, cs[0][1], cs[0][0]);
            build(u, szs[i].ss, vals, cs[1][1], cs[1][0]);
            return;
        }
    }
    sz[u]=csz;
}

vector<int> find_split(int N, int ca, int cb, int cc, vector<int> p, vector<int> q) {
    A.clear(); sz.clear(); found=0;
    n=N; A.resize(n);
    for (ll i=0; i<(ll)p.size(); i++){
        A[p[i]].push_back(q[i]);
        A[q[i]].push_back(p[i]);
    }
    vector<array<ll, 2>> a = {{ca, 1}, {cb, 2}, {cc, 3}};
    sort(a.begin(), a.end()); sz.resize(n);
    vector<int> res;
    dfs(0, 0, a, res);
    if (found) return res;
    else return vector<int>(n, 0);
}

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