Submission #384041

#	Time	Username	Problem	Language	Result	Execution time	Memory
384041		BartolM	Split the Attractions (IOI19_split)	C++17	0 / 100	81 ms	10220 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 <int> mi={a, b, c}, bi={0, 0, 0}, pom={a, b, c};
    sort(mi.begin(), mi.end());
    for (int i=0; i<3; ++i) {
        for (int j=0; j<3; ++j) {
            if (bi[j]) continue;
            if (mi[j]==pom[i]) {
                bi[j]=i+1;
                break;
            }
        }
    }

    dfs(0, -1);
    int node=nadji(0, mi[0], mi[1]);
    if (node==-1) return sol;

//    printf("node: %d\n", node);
//    for (int x:bi) printf("%d\n", x);

    uk=mi[0]; bio[par[node]]=1; oznaci(node, bi[0]);
    uk=mi[1]; bio[par[node]]=0; oznaci(par[node], bi[1]);
    for (int i=0; i<n; ++i) {
        if (!sol[i]) sol[i]=bi[2];
    }
    return sol;
}

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