Submission #422775

#	Time	Username	Problem	Language	Result	Execution time	Memory
422775		TryMax	Split the Attractions (IOI19_split)	C++17	18 / 100	216 ms	23648 KiB

split

#include "split.h"
#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define f first
#define s second

const int N = 1e5 + 10;

int was[N], sz[N], ans[N];
vector<int> g[N], tr[N];

void build_dfs(int u){
    was[u] = 1;
    for(auto v : g[u])
        if(was[v] == 0){
            tr[u].pb(v), tr[v].pb(u);
            build_dfs(v);
        }
}

void paint(int u, int pr, int a, int c){
    if(a <= 0)
        return;
    ans[u] = c;
    --a;
    for(auto v : tr[u])
        if(v != pr && ans[v] == 0){
            paint(v, u, a, c);
            a -= sz[v];
        }
}

void sz_dfs(int u, int pr){
    sz[u] = 1;
    for(auto v : tr[u])
        if(v != pr)
            sz_dfs(v, u), sz[u] += sz[v];
}

bool dfs(int u, int pr, pair<int, int> a, pair<int, int> b, pair<int, int> c){
    for(auto v : tr[u])
        if(v != pr)
            if(dfs(v, u, a, b, c))
                return true;
    if(sz[u] >= b.f && sz[u] <= b.f + c.f){
        paint(u, pr, b.f, b.s);
        return true;
    }
    return false;
}

vector<int> solve(int n, pair<int, int> a, pair<int, int> b, pair<int, int> c){
    for(int i = 0; i < n; ++i)
        was[i] = sz[i] = 0, tr[i].clear();
    build_dfs(0);
    sz_dfs(0, -1);
    vector<int> res(n, 0);
    if(dfs(0, -1, a, b, c)){
        paint(0, -1, a.f, a.s);
        for(int i = 0; i < n; ++i)
            res[i] = (ans[i] == 0 ? c.s : ans[i]);
    }
    return res;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size();
    for(int i = 0; i < m; ++i){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    vector<int> res;
    vector<pair<int, int>> pr;
    pr.pb({a, 1}), pr.pb({b, 2}), pr.pb({c, 3});
    do{
        res = solve(n, pr[0], pr[1], pr[2]);
        if(res[0] != 0)
            return res;
    }while(next_permutation(pr.begin(), pr.end()));
    return res;
}

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