Submission #1047738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047738		NotLinux	Split the Attractions (IOI19_split)	C++17	40 / 100	43 ms	17500 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
const int inf = 1e9 + 7;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    if (a == 1) {
        vector < vector < int > > g(n);
        for (int i = 0; i < sz(p); i++) {
            g[p[i]].push_back(q[i]);
            g[q[i]].push_back(p[i]);
        }
 
 
        vector < int > ans(n, -1);
        vector < int > sizes(n);
 
        int need = 0;
        int T = 0;
        vector < bool > used(n, false);
        function<void(int, int)> choose = [&](int v, int p) {
            if (need == 0)
                return;
            if (used[v]) return;
            used[v] = true;
            need--;
            ans[v] = T;
            for (auto u: g[v]) {
                if (u == p) continue;
                choose(u, v);
            }
        };
        need = b;
        T = 2;
        choose(0, -1);
        for (int i = 0; i < n; i++) {
            if (ans[i] == -1) {
                ans[i] = 1;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (ans[i] == -1) {
                ans[i] = 3;
            }
        }
        return ans;
    }
    else{
        vector < vector < int > > g(n);
        for (int i = 0; i < sz(p); i++) {
            g[p[i]].push_back(q[i]);
            g[q[i]].push_back(p[i]);
        }
 
 
        vector < int > ans(n, 3);
        vector < int > sizes(n);
 
        vector < pair < int , int > > z = {{a, 1},{b, 2},{c, 3}};
        sort(all(z));
        a = z[0].first;
        int ax = z[0].second;
        b = z[1].first;
        int bx = z[1].second;
        int cx = z[2].second;
        std::fill(ans.begin(), ans.end(), cx);
        int splitter = -1;
        int ps;
        vector < int > SZ = {-1, -1};
        vector < int > Tid = {-1, -1};
        vector < bool > used1(n, false);
        function<void(int, int)> calc_sizes = [&](int v, int p) {
            sizes[v] = 1;
            used1[v] = true;
            for (auto u: g[v]) {
                if (u == p) continue;
                if (used1[u]) continue;
                calc_sizes(u, v);
                sizes[v] += sizes[u];
            }
            if (sizes[v] >= a and (n - sizes[v]) >= b) {
                splitter = v;
                SZ[0] = a;
                SZ[1] = b;
                ps = p;
                Tid[0] = ax;
                Tid[1] = bx;
            }
            if (sizes[v] >= b and (n - sizes[v]) >= a) {
                splitter = v;
                SZ[0] = b;
                SZ[1] = a;
                ps = p;
                Tid[0] = bx;
                Tid[1] = ax;
            }
        };
        calc_sizes(0, -1);
        if (splitter == -1) {
            return vector < int >(n, 0);
        }
        int need = 0;
        int T = 0;
        vector < bool > used(n, false);
        function<void(int, int)> choose = [&](int v, int p) {
            if (need == 0)
                return;
            if (used[v]) return;
            used[v] = true;
            need--;
            ans[v] = T;
            for (auto u: g[v]) {
                if (u == p) continue;
                choose(u, v);
            }
        };
        need = SZ[0];
        T = Tid[0];
        choose(splitter, ps);
        need = SZ[1];
        T = Tid[1];
        choose(0, -1);
        return ans;
    }
}

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