제출 #691035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691035		finn__	Split the Attractions (IOI19_split)	C++17	0 / 100	1 ms	340 KiB

split

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

vector<vector<unsigned>> g;
vector<unsigned> preoder, postorder, subtree_size;
vector<bool> has_backward_edge;

bool is_in_subtree(unsigned u, unsigned v)
{
    return preoder[u] < preoder[v] && postorder[u] > postorder[v];
}

pair<unsigned, unsigned> traverse(
    unsigned u, vector<bool> &visited, unsigned i = 0, unsigned j = 0)
{
    preoder[u] = i++;
    visited[u] = 1;
    subtree_size[u] = 1;

    for (unsigned const &v : g[u])
        if (!visited[v])
        {
            tie(i, j) = traverse(v, visited, i, j);
            subtree_size[u] += subtree_size[v];
        }

    postorder[u] = j++;
    return {i, j};
}

void find_backward_edges(unsigned u, vector<bool> &visited)
{
    visited[u] = 1;

    for (unsigned const &v : g[u])
    {
        if (!visited[v])
            find_backward_edges(v, visited);
        else if (!is_in_subtree(u, v))
            has_backward_edge[u] = 1;
    }
}

unsigned find_split_node(unsigned u, vector<bool> &visited, unsigned a)
{
    visited[u] = 1;
    unsigned curr_size = subtree_size[u];
    bool is_min_greater = 1;

    for (unsigned const &v : g[u])
        if (!visited[v] && subtree_size[v] >= a)
            is_min_greater = 0;

    if (is_min_greater)
        for (unsigned const &v : g[u])
        {
            if (!visited[v])
            {
                if (curr_size - subtree_size[v] < a)
                    return u;
                if (has_backward_edge[v])
                    curr_size -= subtree_size[v];
            }
        }

    for (unsigned const &v : g[u])
    {
        if (!visited[v])
        {
            unsigned x = find_split_node(v, visited, a);
            if (x != UINT_MAX)
                return x;
        }
    }

    return UINT_MAX;
}

unsigned dfs_down(
    unsigned u, vector<bool> &visited, vector<int> &ans, unsigned to_add,
    unsigned added_size, unsigned z1, unsigned z2)
{
    visited[u] = 1;
    if (added_size < to_add)
    {
        ans[u] = z1;
        added_size++;
    }
    else
        ans[u] = z2;

    for (unsigned const &v : g[u])
    {
        if (!visited[v] && is_in_subtree(u, v))
            added_size = dfs_down(v, visited, ans, to_add, added_size, z1, z2);
    }

    return added_size;
}

unsigned dfs_up(
    unsigned u, vector<bool> &visited, vector<int> &ans, unsigned to_add,
    unsigned added_size, unsigned z1, unsigned z2)
{
    visited[u] = 1;
    if (added_size < to_add)
    {
        ans[u] = z1;
        added_size++;
    }
    else
        ans[u] = z2;

    for (unsigned const &v : g[u])
    {
        if (!visited[v])
            added_size = dfs_up(v, visited, ans, to_add, added_size, z1, z2);
    }

    return added_size;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    array<pair<unsigned, unsigned>, 3> y;
    y[0] = {a, 1}, y[1] = {b, 2}, y[2] = {c, 3};
    sort(y.begin(), y.end());

    g = vector<vector<unsigned>>(n);
    preoder = vector<unsigned>(n);
    postorder = vector<unsigned>(n);
    subtree_size = vector<unsigned>(n);

    for (size_t i = 0; i < p.size(); i++)
    {
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }

    vector<bool> visited(n, 0);
    traverse(0, visited);
    fill(visited.begin(), visited.end(), 0);

    has_backward_edge = vector<bool>(n, 0);
    find_backward_edges(0, visited);
    fill(visited.begin(), visited.end(), 0);

    unsigned x = find_split_node(0, visited, y[0].first);
    if (x == UINT_MAX)
        return vector<int>(n, 0);
    else
    {
        fill(visited.begin(), visited.end(), 0);
        unsigned p = UINT_MAX;
        for (unsigned const &v : g[x])
            if (!is_in_subtree(x, v))
            {
                p = v;
                break;
            }
        vector<int> ans(n);
        dfs_down(x, visited, ans, subtree_size[x] >= y[1].first ? y[1].first : y[0].first, 0,
                 subtree_size[x] >= y[1].first ? y[1].second : y[0].second,
                 y[2].second);
        dfs_up(p, visited, ans, subtree_size[x] >= y[1].first ? y[0].first : y[1].first, 0,
               subtree_size[x] >= y[1].first ? y[0].second : y[1].second,
               y[2].second);

        return ans;
    }
}

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