제출 #422789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422789		TryMax	Split the Attractions (IOI19_split)	C++17	18 / 100	2085 ms	23752 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], cnt;
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 c){
    if(cnt <= 0 || ans[u] != 0)
        return;
    ans[u] = c;
    --cnt;
    for(auto v : tr[u])
        if(v != pr && ans[v] == 0)
            paint(v, u, c);
}

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){
        cnt = b.f;
        paint(u, pr, b.s);
        return true;
    }
    return false;
}

vector<int> solve(int n, pair<int, int> a, pair<int, int> b, pair<int, int> c, int beg){
    for(int i = 0; i < n; ++i)
        was[i] = sz[i] = 0, tr[i].clear();
    build_dfs(beg);
    sz_dfs(beg, -1);
    vector<int> res(n, 0);
    if(dfs(beg, -1, a, b, c)){
//        for(int i = 0; i < n; ++i)
//            cout << ans[i] << " ";
//        cout << endl;
        cnt = a.f;
        paint(beg, -1, 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});
    for(int i = 0; i < n; ++i){
        sort(pr.begin(), pr.end());
        do{
            res = solve(n, pr[0], pr[1], pr[2], i);
            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