Submission #219772

#	Time	Username	Problem	Language	Result	Execution time	Memory
219772		VEGAnn	Split the Attractions (IOI19_split)	C++14	40 / 100	113 ms	15992 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 100100;
vector<int> res;
vector<int> g[N], vc;
bool mrk[N];
int siz[N], mem, pr[N], col, A[3], C[3];

void dfs(int v){
    if (mrk[v]) return;
    mrk[v] = 1;
    vc.PB(v);

    for (int u : g[v])
        dfs(u);
}

void build_sz(int v, int p){
    siz[v] = 1;
    pr[v] = p;

    for (int u : g[v]){
        if (u == p) continue;
        build_sz(u, v);

        siz[v] += siz[u];
    }
}

void fill(int v, int p){
    if (mem == 0) return;

    mem--;
    res[v] = col;

    for (int u : g[v]){
        if (u == p) continue;

        fill(u, v);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);
	fill(all(res), 0);

	for (int i = 0; i < sz(p); i++){
        g[p[i]].PB(q[i]);
        g[q[i]].PB(p[i]);
	}

	if (sz(p) == n - 1){
        build_sz(0, -1);

        A[0] = a; A[1] = b; A[2] = c;
        C[0] = 1; C[1] = 2; C[2] = 3;

        for (int v = 0; v < n; v++){
            int sub = siz[v], up = n - siz[v];

            bool was = 0;

            for (int i = 0; i < 3 && !was; i++)
                for (int j = 0; j < 3 && !was; j++)
                    if (i != j && A[i] <= sub && A[j] <= up){
                        was = 1;

                        mem = A[i]; col = C[i];
                        fill(v, pr[v]);

                        mem = A[j]; col = C[j];
                        fill(pr[v], v);

                        if (C[i] != 1 && C[j] != 1) col = 1;
                        if (C[i] != 2 && C[j] != 2) col = 2;
                        if (C[i] != 3 && C[j] != 3) col = 3;

                        for (int &cr : res)
                            if (cr == 0)
                                cr = col;

                        break;
                    }

            if (was) break;
        }

        return res;
	}

	bool was = 0;

	for (int i = 0; i < n; i++)
        if (sz(g[i]) == 1){
            was = 1;
            dfs(i);
            break;
        }

    if (!was) dfs(0);

	for (int i = 0; i < a; i++)
        res[vc[i]] = 1;

	for (int i = 0; i < b; i++)
        res[vc[a + i]] = 2;

	for (int i = 0; i < c; i++)
        res[vc[a + b + i]] = 3;

	return res;
}

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