Submission #837735

#	Time	Username	Problem	Language	Result	Execution time	Memory
837735		finn__	Split the Attractions (IOI19_split)	C++17	18 / 100	76 ms	24152 KiB

split

#include <bits/stdc++.h>

#include "split.h"

using namespace std;

constexpr size_t N = 100000;

vector<int> g[N], t[N], color;
int n, a, b, h[N], l[N], s[N], label[3];
bitset<N> visited;

void build_dfs_tree(int u)
{
    visited[u] = 1;
    l[u] = h[u];
    s[u] = 1;

    for (auto const &v : g[u])
        if (!visited[v])
        {
            h[v] = h[u] + 1;
            t[u].push_back(v);
            build_dfs_tree(v);
            l[u] = min(l[u], l[v]);
            s[u] += s[v];
        }
        else
            l[u] = min(l[u], h[v]);
}

void label_component(int u, int size, int l)
{
    queue<int> q({u});
    while (size--)
    {
        assert(!q.empty());
        int x = q.front();
        q.pop();
        color[x] = l;
        for (auto const &v : t[x])
            q.push(v);
    }
}

bool dfs(int u, int p = -1)
{
    visited[u] = 1;

    for (auto const &v : g[u])
        if (!visited[v])
            if (dfs(v, u))
                return 1;

    if (s[u] >= a)
    {
        if (p == -1)
            return 1;

        t[p].erase(find(t[p].begin(), t[p].end(), u));

        int y = s[u];

        if (n - y < b || (y >= b && n - y < a))
            for (size_t i = 0; i < t[u].size(); ++i)
            {
                int v = t[u][i];
                if (l[v] < h[u])
                {
                    if (y - s[v] < a)
                        break; // We know the graph outside u's subtree is >= b
                    y -= s[v];
                    swap(t[u][i], t[u].back());
                    --i;
                    t[u].pop_back();
                    t[0].push_back(v);
                }
            }

        if (n - y >= b)
        {
            label_component(u, a, label[0]);
            label_component(0, b, label[1]);
            for (int &x : color)
                if (!x)
                    x = label[2];
        }
        else if (y >= b)
        {
            label_component(u, b, label[1]);
            label_component(0, a, label[0]);
            for (int &x : color)
                if (!x)
                    x = label[2];
        }

        return 1;
    }

    return 0;
}

vector<int> find_split(int n_, int a_, int b_, int c, vector<int> p, vector<int> q)
{
    int const sizes[3] = {a_, b_, c};
    label[0] = 1, label[1] = 2, label[2] = 3;
    sort(label, label + 3, [&](auto const &i, auto const &j)
         { return sizes[i - 1] < sizes[j - 1]; });

    n = n_, a = sizes[label[0] - 1], b = sizes[label[1] - 1];
    for (size_t i = 0; i < p.size(); ++i)
        g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
    build_dfs_tree(0);
    visited.reset();
    color.resize(n);
    dfs(0);
    return color;
}

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