Submission #384044

#	Time	Username	Problem	Language	Result	Execution time	Memory
384044		BartolM	Split the Attractions (IOI19_split)	C++17	22 / 100	103 ms	13292 KiB

split

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;

int n, m;
vector <int> ls[N], sol;
int cnt[N], par[N], bio[N];

void dfs(int node, int rod) {
    cnt[node]=1;
    par[node]=rod;
    for (int sus:ls[node]) {
        if (sus==par[node]) continue;
        dfs(sus, node);
        cnt[node]+=cnt[sus];
    }
}

int nadji(int node, int a, int b) {
    if (cnt[node]>=a && n-cnt[node]>=b) return node;
    for (int sus:ls[node]) {
        if (sus==par[node]) continue;
        int ret=nadji(sus, a, b);
        if (ret!=-1) return ret;
    }
    return -1;
}

int uk;

void oznaci(int node, int ozn) {
    if (uk==0) return;
    sol[node]=ozn; uk--;
    bio[node]=1;
    for (int sus:ls[node]) {
        if (bio[sus]) continue;
        oznaci(sus, ozn);
    }
}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
    n=nn; m=p.size();
    sol.resize(n, 0);
    for (int i=0; i<m; ++i) {
        ls[p[i]].pb(q[i]);
        ls[q[i]].pb(p[i]);
    }
    assert(m==n-1);

    vector <pii> mi={{a, 1}, {b, 2}, {c, 3}};
    sort(mi.begin(), mi.end());

    dfs(0, -1);
    for (int e=0; e<2; ++e) {
        int node=nadji(0, mi[0].X, mi[1].X);
        if (node!=-1) {
            uk=mi[0].X; bio[par[node]]=1; oznaci(node, mi[0].Y);
            uk=mi[1].X; bio[par[node]]=0; oznaci(par[node], mi[1].Y);
            for (int i=0; i<n; ++i) if (!sol[i]) sol[i]=mi[2].Y;
            return sol;
        }
        swap(mi[0], mi[1]);
    }
    return sol;
}

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