Submission #422757

#	Time	Username	Problem	Language	Result	Execution time	Memory
422757		TryMax	Split the Attractions (IOI19_split)	C++17	0 / 100	145 ms	21716 KiB

split

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

using namespace std;

#define pb push_back

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, int a, int b, int c){
    for(auto v : tr[u])
        if(v != pr)
            if(dfs(v, u, a, b, c))
                return true;
    if(sz[u] >= b && sz[u] <= b + c){
        paint(u, pr, b, 2);
        return true;
    }
    return false;
}

vector<int> solve(int n, int a, int b, 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, 1);
        for(int i = 0; i < n; ++i)
            res[i] = (ans[i] == 0 ? 3 : 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, pr;
    pr.pb(a), pr.pb(b), pr.pb(c);
    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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36