Submission #283171

#	Time	Username	Problem	Language	Result	Execution time	Memory
283171		hoanghq2004	Split the Attractions (IOI19_split)	C++14	100 / 100	171 ms	25240 KiB

split

#include <bits/stdc++.h>

#define split

#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], d[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);
            d[v] = d[u] + 1;
            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 = 0; 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;
        }
    }
    for (int u = 0; u < n; ++u)
        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;
            paint(0, a.first, a.second);
            cnt = n - sz[u];

            for (auto v: E[u])
            {
                if (low[v] < num[u] && cnt + sz[v] <= a.first)
                {
                    paint(v, a.first, a.second);
                    cnt += sz[v];
                    if (cnt == a.first) break;
                    else continue;
                }
                if (low[v] < num[u] && cnt + sz[v] > a.first)
                {
                    int pivot = num[u];
//                    cout << low[v] << " " << pivot << "\n";
                    queue <int> q;
                    vector <int> backward;
                    q.push(v);
                    while (!q.empty())
                    {
                        int u = q.front();
                        q.pop();
                        int ok = 0;
                        for (auto v: E[u])
                        {
                            if (low[v] < pivot)
                            {
                                ok = 1;
                                q.push(v);
                            }
                        }
                        if (!ok) backward.push_back(u);
                    }
//                    cout << backward.size() << "\n";

//                    cout << backward[0] << ' '<< v << "\n";

                    for (auto root: backward)
                    {
                        q.push(root);
                        while (!q.empty())
                        {
                            int u = q.front();
                            q.pop();
                            ++cnt;
                            C[u] = a.second;
                            if (cnt == a.first) goto label;
//                            assert(cnt < a.first);
                            for (auto v: E[u])
                                q.push(v);
                        }
                    }
                    q.push(v);
                    stack <int> stk;
                    while (!q.empty())
                    {
                        int u = q.front();
                        q.pop();
                        stk.push(u);
                        for (auto v: E[u])
                            if (!C[v])
                                q.push(v);
                    }
                    while (!stk.empty())
                    {
                        int u = stk.top();
                        stk.pop();
                        C[u] = a.second;
                        ++cnt;
                        if (cnt == a.first) goto label;
//                        assert(cnt < a.first);
                    }
                }
            }
            label:;
            C[u] = 0;
            paint(u, b.first, b.second);

            for (int i = 0; i < n; ++i)
                if (!C[i]) C[i] = c.second;
            return C;
        }
    return C;
}

#ifndef split
int main() {
    freopen("split.inp", "r", stdin);
    freopen("split.out", "w", stdout);


	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector <int> p(m), q(m);
	for (int i = 0; i < m; ++i)
		assert(2 == scanf("%d%d", &p[i], &q[i]));

	vector <int> result = find_split(n, a, b, c, p, q);

	for (int i = 0; i < result.size(); ++i)
		printf("%s%d", ((i > 0) ? " " : ""), result[i]);
	printf("\n");
	return 0;
}
#endif

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