제출 #281774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281774		hoanghq2004	Split the Attractions (IOI19_split)	C++14	40 / 100	172 ms	24616 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;
const int N = 100005;
int n;
pair <int, int> a, b, c;
vector <int> C, adj[N], E[N];
int sz[N], check[N];
int times, low[N], num[N];

void dfs(int u, int p)
{
    num[u] = low[u] = ++times;
    sz[u] = 1;
    check[u] = 1;
    for (auto v: adj[u])
    {
        if (v == p) continue;
        if (!num[v])
        {
            E[u].push_back(v);
            dfs(v, u);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            if (sz[v] >= a.first) check[u] = 0;
        }
        else low[u] = min(low[u], num[v]);
    }
}


void paint(int u, int num, int cl)
{
    queue <int> q;
    q.push(u);
    int cnt = 0;
    if (!C[u])
    {
        C[u] = cl;
        cnt = 1;
    }
    if (cnt == num) return;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v: E[u])
            if (!C[v])
            {
                ++cnt;
                C[v] = cl;
                q.push(v);
                if (num == cnt) return;
            }
    }
}


vector <int> find_split(int _n, int _a, int _b, int _c, vector <int> u, vector <int> v)
{
    n = _n;
    a = {_a, 1}, b = {_b, 2}, c = {_c, 3};

    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);

    assert(a <= b && b <= c);

    int m = (int)v.size();
    C = vector <int> (n, 0);

    for (int i = 0; i < m; i ++)
    {
        adj[v[i]].push_back(u[i]);
        adj[u[i]].push_back(v[i]);
    }
    dfs(0, 0);
    for (int u = 1; u < n; ++u)
    {
        if (check[u] && sz[u] >= a.first && n - sz[u] >= a.first)
        {
            if (sz[u] <= n - sz[u])
            {
                paint(u, a.first, a.second);
                paint(0, b.first, b.second);
            }
            else
            {
                paint(u, b.first, b.second);
                paint(0, a.first, a.second);
            }
            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
        if (check[u] && n - sz[u] < a.first)
        {
            int cnt = 0;
            for (auto v: E[u])
                if (low[v] < num[u]) cnt += sz[v];
            if (cnt + n - sz[u] < a.first) continue;

            C[u] = b.second;
            cnt = 1;
            for (auto v: E[u])
                if (low[v] >= num[u])
                {
                    paint(v, b.first - cnt, b.second);
                    cnt += sz[v];
                    if (sz[v] <= 0) break;
                }
            paint(0, a.first, a.first);
            cnt = n - sz[u];
            for (int i = 0; i < n; ++i)
                if (!C[i] && low[i] < num[u])
                {
                    C[i] = a.second;
                    ++cnt;
                    if (cnt == a.first) break;
                }
            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
    }
    return C;
}

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