Submission #1237357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237357		jer033	Split the Attractions (IOI19_split)	C++20	40 / 100	73 ms	17192 KiB

split

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

int centroid_find(int n, vector<vector<int>> (&edges))
{
    //create a spanning tree
    //vector<vector<int>> new_edges(n);
    vector<int> parent(n, -2);
    vector<int> nodes;

    nodes.push_back(0);
    parent[0] = -1;
    
    int curr = 0;
    int total = 1;

    while (curr < total)
    {
        int x = nodes[curr]; curr++;
        for (int y: edges[x])
        {
            if (parent[y] == -2)
            {
                parent[y] = x;
                nodes.push_back(y);
                total++;
                //new_edges[]
            }
        }
    }

    vector<int> subtreesize(n, 1);
    for (int i=n-1; i>0; i--)
    {
        int x = nodes[i];
        subtreesize[parent[x]] += subtreesize[x];
    }

    //now identify the centroid
    int bes = n+1;
    int cap = (n+1)/2;
    int centroid = -1;
    for (int i=0; i<n; i++)
        if ((subtreesize[i]<bes) and (subtreesize[i]>=cap))
        {
            bes = subtreesize[i];
            centroid = i;
        }
    return centroid;
}

vector<int> find_split_wlog(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<vector<int>> edges(n);
    int e = p.size();
    for (int i=0; i<e; i++)
    {
        int pp = p[i];
        int qq = q[i];
        edges[pp].push_back(qq);
        edges[qq].push_back(pp);
    }

    int root = centroid_find(n, edges);
    //cout << root << '\n';

    //step 3: perform a dfs and identify whether its possible or not

    vector<int> parent(n, -2);
    stack<pair<int, int>> nodes;
    vector<int> push_order;
    vector<vector<int>> children(n);

    parent[root] = -1;
    nodes.push({root, 0});
    push_order.push_back(root);

    while (!nodes.empty())
    {
        pair<int, int> info = nodes.top();
        int x = info.first; int y = info.second;
        nodes.pop();
        if ((y+1)<edges[x].size())
            nodes.push({x, y+1});
        int z = edges[x][y];
        if (parent[z]==-2)
        {
            parent[z] = x;
            nodes.push({z, 0});
            push_order.push_back(z);
            children[x].push_back(z);
        }
    }

    vector<int> subtreesize(n, 1);
    for (int i=n-1; i>0; i--)
    {
        int x = push_order[i];
        subtreesize[parent[x]] += subtreesize[x];
        //cout << x << subtreesize[x] << '\n';
    }
    
    int node_min = n+1;
    int root_a = -1;
    for (int i=0; i<n; i++)
        if ((i!=root) and (subtreesize[i] < node_min) and (subtreesize[i]>=a))
        {
            node_min = subtreesize[i];
            root_a = i;
        }
    
    if (root_a == -1)
    {
        vector<int> ans(n, 0);
        return ans;
    }

    //then a solution is possible
    vector<int> ans(n, 3);
    queue<int> group_a;
    group_a.push(root_a);
    ans[root_a] = 1;
    int members = 1;
    while (members < a)
    {
        int x = group_a.front(); group_a.pop();
        for (int y: children[x])
            if (members < a)
            {
                ans[y] = 1;
                group_a.push(y);
                members++;
            }
    }

    queue<int> group_b;
    group_b.push(root);
    ans[root] = 2;
    members = 1;
    while (members < b)
    {
        int x = group_b.front(); group_b.pop();
        for (int y: children[x])
            if ((members < b) and (ans[y]==3))
            {
                ans[y] = 2;
                group_b.push(y);
                members++;
            }
    }

    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    //0 2 3 1
    //112223
    //223331
	vector<int> rewrite = {0, 1, 2, 3};
    for (int i=0; i<5; i++)
    {
        if (a>b)
        {
            swap(a, b);
            swap(rewrite[1], rewrite[2]);
        }
        if (b>c)
        {
            swap(b, c);
            swap(rewrite[2], rewrite[3]);
        }
    }

    vector<int> ans = find_split_wlog(n, a, b, c, p, q);
    for (int i=0; i<n; i++)
    {
        ans[i] = rewrite[ans[i]];
        /*if (ans[i]==rewrite[0])
            ans[i] = 0;
        else if (ans[i]==rewrite[1])
            ans[i] = 1;
        else if (ans[i]==rewrite[2])
            ans[i] = 2;
        else if (ans[i]==rewrite[3])
            ans[i] = 3;*/
    }
    return ans;
}

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