Submission #476508

#	Time	Username	Problem	Language	Result	Execution time	Memory
476508		Lam_lai_cuoc_doi	Split the Attractions (IOI19_split)	C++17	100 / 100	184 ms	23444 KiB

split

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;

vector<pair<int, int>> adj[N];
bool inused[N];
int cnt[N], n;
pair<int, int> a[3], par[N];

void dfs(int v, int p = 0)
{
    cnt[v] = 1;
    for (auto i : adj[v])
        if (i.first != p && !cnt[i.first])
        {
            inused[i.second] = 1;
            par[i.first] = make_pair(v, i.second);
            dfs(i.first, v);
            cnt[v] += cnt[i.first];
        }
}

vector<int> Do()
{
    int cnt1(0);

    vector<int> ans(n, 0);

    function<void(int, int, pair<int, int>)> Colored = [&](int v, int p, pair<int, int> a)
    {
        ++cnt1;
        ans[v] = a.second;
        if (cnt1 == a.first)
            return;

        for (auto i : adj[v])
            if (inused[i.second] && i.first != p)
            {
                Colored(i.first, v, a);
                if (cnt1 == a.first)
                    return;
            }
    };

    for (int i = 1; i < n; ++i)
        if (cnt[i] >= a[0].first)
        {
            int sz(cnt[i]);
            bool ok(1);

            for (auto j : adj[i])
                if (par[j.first].first == i)
                {
                    if (cnt[j.first] >= a[0].first)
                    {
                        ok = 0;
                        break;
                    }
                }

            if (!ok)
                continue;

            //cout << i << " " << cnt[i] << " " << a[0].first << "\n";

            vector<pair<int, int>> off;

            for (auto j : adj[i])
                if (par[j.first].first == i)
                {
                    if (adj[j.first][0].first != i && sz - cnt[j.first] >= a[0].first)
                    {
                        sz -= cnt[j.first];
                        off.emplace_back(j);
                    }
                    else if (sz - cnt[j.first] <= a[0].first)
                    {
                        for (auto t : off)
                        {
                            inused[t.second] = 0;
                            inused[adj[t.first][0].second] = 1;
                        }
                        inused[par[i].second] = 0;
                        //cout << i << " " << par[i].first << " " << sz << " " << a[0].second << "\n";

                        cnt1 = 0;
                        Colored(i, -1, a[0]);
                        cnt1 = 0;
                        Colored(par[i].first, -1, a[1]);

                        for (auto &t : ans)
                            if (t == 0)
                                t = a[2].second;

                        for (auto t : off)
                        {
                            inused[t.second] = 1;
                            inused[adj[t.first][0].second] = 0;
                        }
                        inused[par[i].second] = 1;

                        goto done;
                    }
                    //cout << sz << "\n";
                }

            if (n - sz >= a[1].first)
            {
                inused[par[i].second] = 0;
                for (auto t : off)
                {
                    inused[t.second] = 0;
                    inused[adj[t.first][0].second] = 1;
                }

                cnt1 = 0;
                Colored(i, -1, a[0]);
                cnt1 = 0;
                Colored(par[i].first, -1, a[1]);

                inused[par[i].second] = 1;
                for (auto t : off)
                {
                    inused[t.second] = 1;
                    inused[adj[t.first][0].second] = 0;
                }

                for (auto &t : ans)
                    if (t == 0)
                        t = a[2].second;

                break;
            }
            else if (n - sz >= a[0].first)
            {
                inused[par[i].second] = 0;
                for (auto t : off)
                {
                    inused[t.second] = 0;
                    inused[adj[t.first][0].second] = 1;
                }

                cnt1 = 0;
                Colored(i, -1, a[1]);
                cnt1 = 0;
                Colored(par[i].first, -1, a[0]);

                inused[par[i].second] = 1;
                for (auto t : off)
                {
                    inused[t.second] = 1;
                    inused[adj[t.first][0].second] = 0;
                }

                for (auto &t : ans)
                    if (t == 0)
                        t = a[2].second;

                break;
            }
        }
done:;

    return ans;
}

vector<int> find_split(int nn, int A, int B, int C, vector<int> p, vector<int> q)
{
    int m = p.size();
    n = nn;
    vector<int> ans(n, 0);
    a[0] = make_pair(A, 1);
    a[1] = make_pair(B, 2);
    a[2] = make_pair(C, 3);

    sort(a, a + 3);

    for (int i = 0; i < m; ++i)
    {
        adj[p[i]].emplace_back(q[i], i);
        adj[q[i]].emplace_back(p[i], i);
    }

    dfs(0);

    for (int i = 0; i < n; ++i)
        sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y)
             { return cnt[x.first] > cnt[y.first]; });

    ans = Do();

    if (count(ans.begin(), ans.end(), '0') != 0)
    {
        swap(a[0], a[1]);
        ans = Do();
    }

    return ans;
}

void Read()
{
    int n, m, a, b, c;
    cin >> n >> m;
    cin >> a >> b >> c;
    vector<int> u(m), v(m);
    for (int i = 0; i < m; ++i)
        cin >> u[i] >> v[i];

    vector<int> ans = find_split(n, a, b, c, u, v);

    for (auto i : ans)
        cout << i << " ";
}

void Solve()
{
    /*
        9 4 2 3 10
        0 1
        0 2
        0 3
        0 4
        0 8
        0 6 
        1 7
        4 5
        3 7
        6 5

        6 2 2 2 5
        0 1
        0 2
        0 3
        0 4
        0 5

    */
}

Compilation message (stderr)

split.cpp: In function 'void read(T&)':
split.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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