Submission #397971

#	Time	Username	Problem	Language	Result	Execution time	Memory
397971		snasibov05	Split the Attractions (IOI19_split)	C++14	22 / 100	628 ms	1048580 KiB

split

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

#define pb push_back
#define oo 1000000000
#define pii pair<int, int>

using namespace std;

const int nmax = 1e5 + 5;

vector<int> ed[nmax];
vector<pii> subtr[nmax];

int cnt = 0;

vector<int> answer;

int dfs(int v, int pr, int n){

    int k = 0;

    for (auto to : ed[v]){
        if (to == pr) continue;
        subtr[v].pb({dfs(to, v, n), to});
        k += subtr[v].back().first;
    }

    if (n - k - 1 > 0) subtr[v].pb({n - k - 1, pr});
    return k + 1;
}

void number(int v, int pr, int k){
    if (cnt == 0) return;
    answer[v] = k;
    cnt--;
    for (auto x : ed[v]){
        if (x == pr) continue;
        number(x, v, k);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {

    answer.resize(n);

    int m = p.size();
    for (int i = 0; i < m; ++i) {
        ed[p[i]].pb(q[i]);
        ed[q[i]].pb(p[i]);
    }

    dfs(0, -1, n);

    int v[4] = {oo, a, b, c};
    int mn[3];

    int mni = 0;
    for (int i = 1; i <= 3; ++i) {
        if (v[i] < v[mni]) mni = i;
    }

    mn[0] = mni;

    int smni = 0;
    for (int i = 1; i <= 3; ++i) {
        if (mni == i) continue;
        if (v[i] < v[smni]) smni = i;
    }

    mn[1] = smni;

    int k = 0;
    for (int i = 1; i <= 3; ++i) {
        if (i != smni && i != mni) k = i;
    }

    mn[2] = k;

    bool flag = false;

    for (int i = 0; i < n; ++i) {
        if (subtr[i].size() == 1) continue;
        sort(subtr[i].begin(), subtr[i].end());
        auto it = lower_bound(subtr[i].begin(), subtr[i].end(), make_pair(v[mn[0]], 0));
        if (it == subtr[i].end()) continue;
        if (n - it->first >= v[mn[1]]){
            cnt = v[mn[0]];
            number(it->second, i, mn[0]);
            answer[i] = mn[1];
            cnt = v[mn[1]] - 1;
            for (auto x : subtr[i]){
                if (x == *it) continue;
                number(x.second, i, mn[1]);
            }

            flag = true;
            break;
        }

    }

    if (!flag) return answer;

    for (int i = 0; i < n; ++i) {
        if (answer[i] == 0) answer[i] = mn[2];
    }

    return answer;
}

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