Submission #405642

#	Time	Username	Problem	Language	Result	Execution time	Memory
405642		Tc14	Split the Attractions (IOI19_split)	C++17	22 / 100	691 ms	1048580 KiB

split

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int n, v1, v2;
pii x, y, z, curr;
bool valid;
ve<ve<int>> T;
ve<int> Ans;

int dfs(int u, int p) {

    int s = 1;
    for (int v : T[u]) {
        if (v != p) {
            s += dfs(v, u);
        }
    }

    if (s < n - s) {
        if (s >= x.first && n - s >= y.first) {
            v1 = u;
            v2 = p;
            valid = true;
        }
    }
    else {
        if (n - s >= x.first && s >= y.first) {
            v1 = p;
            v2 = u;
            valid = true;
        }
    }

    return s;
}

void assign(int u, int p, int b) {

    if (curr.first > 0) {
        Ans[u] = curr.second;
        curr.first--;
    }

    for (int v : T[u]) {
        if (v != p && v != b) {
            assign(v, u, b);
        }
    }
}

ve<int> find_split(int _n, int a, int b, int c, ve<int> p, ve<int> q) {

    int m;

    n = _n;
    T = ve<ve<int>>(n);

    m = (int)p.size();
    for (int i = 0; i < m; i++) {
        T[p[i]].push_back(q[i]);
        T[q[i]].push_back(p[i]);
    }

    ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
    sort(A.begin(), A.end());
    x = A[0];
    y = A[1];
    z = A[2];

    valid = false;
    dfs(0, -1);

    if (valid) {
        Ans = ve<int>(n, z.second);
        curr = x;
        assign(v1, -1, v2);
        curr = y;
        assign(v2, -1, v1);
    }
    else Ans = ve<int>(n, 0);

	return Ans;
}

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