Submission #1237189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237189		Ghulam_Junaid	Split the Attractions (IOI19_split)	C++17	22 / 100	549 ms	1114112 KiB

split

#include <bits/stdc++.h>
#include "split.h"
// #include "grader.cpp"
using namespace std;

const int N = 2e5 + 10;
int n, m, a, b, c, sz[N], par[N], comp_sz[4];
vector<int> g[N], seen, res;

void dfs(int v, int p = -1){
    par[v] = p;
    sz[v] = 1;
    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
        sz[v] += sz[u];
    }
}

void get(int v, int x, int target, int p = -1){
    seen.push_back(v);
    for (int u : g[v]){
        if (u == p or u == x) continue;
        if (seen.size() < target)
            get(u, x, target, v);
    }
}

void get_sub(int v, int x, int target){
    seen.push_back(v);
    for (int u : g[v]){
        if (u == par[v] or u == x) continue;
        if (seen.size() < target)
            get_sub(u, x, target);
    }
}

// void reroot(int v, int p = -1){
//     for (int u : g[v]){

//     }
// }

vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> p, vector<int> q) {
	n = nn, a = aa, b = bb, c = cc, m = p.size();
    comp_sz[1] = aa, comp_sz[2] = bb, comp_sz[3] = cc;

    a = min({aa, bb, cc});
    c = max({aa, bb, cc});
    b = n - a - c;
    for (int i = 0; i < m; i ++){
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    res.resize(n, 0);

    int r = 0;
    for (int i = 1; i < n; i ++)
        if (g[r].size() < g[i].size())
            r = i;

    dfs(r);
    for (int v = 0; v < n; v ++){
        if (sz[v] >= a and n - sz[v] >= b){
            get_sub(v, -1, a);
            for (int col = 1; col <= 3; col ++){
                if (comp_sz[col] == a){
                    for (int x : seen)
                        res[x] = col;
                    comp_sz[col] = -1;
                    break;
                }
            }
            seen.clear();

            get(r, v, b);
            for (int col = 1; col <= 3; col ++){
                if (comp_sz[col] == b){
                    for (int x : seen)
                        res[x] = col;
                    comp_sz[col] = -1;
                    break;
                }
            }
            seen.clear();

            for (int col = 1; col <= 3; col ++){
                if (comp_sz[col] == -1) continue;
                for (int i = 0; i < n; i ++)
                    if (!res[i])
                        res[i] = col;
            }

            return res;
        }
    }

	return res;
}

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