Submission #397948

#	Time	Username	Problem	Language	Result	Execution time	Memory
397948		snasibov05	Split the Attractions (IOI19_split)	C++14	Compilation error	0 ms	0 KiB

split

#include "split.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];

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, int num){
    if (num == 0) return;
    answer[v] = k;
    for (auto x : ed[v]){
        if (x == pr) continue;
        number(v, x, k, num-1);
    }
}

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].rbegin(), subtr[i].rend());
        if (subtr[i][1].first >= v[mn[0]] && subtr[i][0].first + 1 >= v[mn[1]]){
            number(subtr[i][1].second, i, mn[0], v[mn[0]]);
            number(subtr[i][0].second, i, mn[1], v[mn[1]] - 1);
            answer[i] = mn[1];
            flag = true;
            break;
        }
        if (subtr[i][1].first + 1 >= v[mn[0]] && subtr[i][0].first >= v[mn[1]]){
            number(subtr[i][1].second, i, mn[0], v[mn[0]] - 1);
            number(subtr[i][0].second, i, mn[1], v[mn[1]]);
            answer[i] = mn[0];
            flag = true;
            break;
        }
    }

    if (!flag) return answer;

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

    return answer;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:80:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   80 |         sort(subtr[i].rbegin(), subtr[i].rend());
      |         ^~~~
      |         short