Submission #143572

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

split

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

const int MAXN = 100010;
int subtree_size[MAXN];
vector<int> adj[MAXN];

void dfs(int src = 0, int prev = -1) {
    //printf("dfs %d %d\n", src, prev);
    subtree_size[src] = 1;
    for(auto &xt : adj[src]) {
        if(xt - prev) {
            dfs(xt, src);
            subtree_size[src] += subtree_size[xt];
        }
    }
}

vector<int> get_solution(vector<int> v1, int n1, vector<int> v2, int n2, int n) {
    vector<int> ans(n, 6 - n1 - n2);
    for(auto &x : v1) {
        ans[x] = n1;
    }
    for(auto &x : v2) {
        ans[x] = n2;
    }
    return ans;
}

bool marked[MAXN];
vector<int> extract(int src, int wrong, int sz) {
    for(int i = 0; i < MAXN; i++) {
        marked[i] = false;
    }
    marked[wrong] = true;
    vector<int> ans;
    stack<int> nodes;
    nodes.push(src);
    marked[src] = true;
    while((int)ans.size() < sz) {
        int node = nodes.top();
        nodes.pop();
        ans.push_back(node);
        for(auto &x : adj[node]) {
            if(!marked[x]) {
                marked[x] = true;
                nodes.push(x);
            }
        }
    }
    return ans;
}

vector<int> blank(int n) {
    vector<int> ans(n, 0);
    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    pair<int, int> arr[] = {{a, 1}, {b, 2}, {c, 3}};
    sort(arr, arr + 3);
    int A = arr[0].first, B = arr[1].first, C = arr[2].first;
    int m = (int)p.size();
    for(int i = 0; i < m; i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    dfs();
    //for(int i = 0; i < n; i++) {
    //   printf("subtree_size[%d] = %d\n", i, subtree_size[i]);
    //}
    for(int i = 0; i < m; i++) {
        int u = p[i], v = q[i];
        if(subtree_size[u] > subtree_size[v]) swap(u, v);
        int under = subtree_size[u];
        int rest = n - under;
        if(under >= A && rest >= A) {
            //printf("found for edge %d - %d\n", u, v);
            //we've got a solution
            vector<int> set_A, set_B;
            if(under < rest) {
                set_A = extract(u, v, A);
                set_B = extract(v, u, B);
            } else {
                set_A = extract(v, u, A);
                set_B = extract(u, v, B);
            }
            return get_solution(set_A, arr[0].second, set_B, arr[1].second, n);
        }
    }
    //there is no edge connecting two subtrees of sizes >= a
    //meaning that it's a star with all subtrees attached of size < a
    //in tree, there is no such solution
    return blank(n);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:63:45: warning: unused variable 'C' [-Wunused-variable]
     int A = arr[0].first, B = arr[1].first, C = arr[2].first;
                                             ^

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