Submission #220052

#	Time	Username	Problem	Language	Result	Execution time	Memory
220052		VEGAnn	Split the Attractions (IOI19_split)	C++14	100 / 100	187 ms	25208 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, children[N];
bool mrk[N];
int A[3], C[3], mrk_col[N], h[N], mn_h[N], pr[N], siz[N], mem = 0;

void dfs(int v, int p){
    pr[v] = p;
    siz[v] = 1;
    mrk[v] = 1;
    mn_h[v] = h[v];

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

        if (!mrk[u]) {
            children[v].PB(u);
            h[u] = h[v] + 1;

            dfs(u, v);

            mn_h[v] = min(mn_h[v], mn_h[u]);
            siz[v] += siz[u];
        } else mn_h[v] = min(mn_h[v], h[u]);
    }
}

void col(int v, int cl){
    mrk_col[v] = cl;

    for (int u : children[v])
        col(u, cl);
}

void DFS(int v, int cl, int rlc){
    if (mrk[v]) return;
    if (mem == 0) return;

    mem--;
    mrk[v] = 1;
    res[v] = rlc;

    for (int u : g[v])
        if (mrk_col[u] == cl)
            DFS(u, cl, rlc);
}

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 = sz(p) - 1; i >= 0; i--){
        g[p[i]].PB(q[i]);
        g[q[i]].PB(p[i]);
	}

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

	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}
	if (A[1] > A[2]) {
        swap(A[1], A[2]);
        swap(C[1], C[2]);
	}
	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}

    dfs(0, -1);

    for (int v = 0; v < n; v++){
        bool ok = bool(siz[v] >= A[0]);

        for (int u : children[v])
            ok &= bool(siz[u] < A[0]);

        if (!ok) continue;

        col(0, 1);
        col(v, 2);

        int real_siz = siz[v];

        for (int u : children[v])
            if (mn_h[u] < h[v] && real_siz - siz[u] >= A[0]){
                real_siz -= siz[u];
                col(u, 1);
            }

        for (int t1 = 0; t1 < 2; t1++){
            int t2 = 1 - t1;

            if (real_siz >= A[t1] && n - real_siz >= A[t2]){
                fill(mrk, mrk + n, 0);

                mem = A[t2];
                DFS(pr[v], 1, C[t2]);

                mem = A[t1];
                DFS(v, 2, C[t1]);

                for (int &cr : res)
                    if (cr == 0)
                        cr = C[2];

                return res;
            }
        }
    }

	return res;
}

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