제출 #281532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281532		hoanghq2004	Split the Attractions (IOI19_split)	C++14	0 / 100	568 ms	1048580 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];
int sz[N], check[N];

void dfs(int u, int p)
{
    sz[u] = 1;
    check[u] = 1;
    for (auto v: adj[u])
    {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] >= a.first) check[u] = 0;
    }
    if (sz[u] < a.first || n - sz[u] < a.first) check[u] = 0;
}


void color(int u, int num, int cl)
{
    queue <int> q;
    q.push(u);
    C[u] = cl;
    int cnt = 1;
    if (cnt == num) return;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v: adj[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])
        {
            if (sz[u] <= n - sz[u])
            {
                color(u, a.first, a.second);
                color(0, b.first, b.second);
            }
            else
            {
                color(u, b.first, b.second);
                color(0, a.first, a.second);
            }
            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
    return C;
}

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