Submission #1305205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305205		andrei_iorgulescu	Split the Attractions (IOI19_split)	C++20	40 / 100	56 ms	16824 KiB

split

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

using namespace std;

mt19937 rng(15);///everybody wants to...

const int BB = 3e7;

int n, a, b, c, k;
vector<int> g[100005];
vector<int> sol;
int sz[100005];
int dp[100005];
bool fs;

int sub, col, cate, cate2, tat;
bool viz[100005];
int h[100005];

void dfs(int nod, int tt)
{
    sz[nod] = 1;
    //dp[nod] = n + 1;
    viz[nod] = true;
    for (auto vecin : g[nod])
    {
        if (!viz[vecin])
        {
            h[vecin] = 1 + h[nod];
            dfs(vecin, nod);
            sz[nod] += sz[vecin];
            //dp[nod] = min(dp[nod], dp[vecin]);
        }
    }
    if (!fs and sz[nod] >= a and sz[nod] <= n - a)
    {
        fs = true;
        if (sz[nod] < b)
            sub = nod, col = 1, cate = a, cate2 = b, tat = tt;
        else
            sub = nod, col = 2, cate = b, cate2 = a, tat = tt;
    }
}

int ct;

void cd(int nod, int tt, int cl)
{
    if (ct == 0)
        return;
    sol[nod] = cl;
    ct--;
    viz[nod] = true;
    for (auto vecin : g[nod])
    {
        if (vecin != tt and vecin != sub and h[vecin] == 1 + h[nod])
            cd(vecin, nod, cl);
    }
}

vector<int> find_split(int N, int A, int B, int C, vector<int> U, vector<int> V)
{
    n = N;
    a = A;
    b = B;
    c = C;
    vector<int> ord(4);
    vector<int> ordm1(4);
    ord[0] = 0;
    ord[1] = 1, ord[2] = 2, ord[3] = 3;
    if (a > b)
        swap(a, b), swap(ord[1], ord[2]);
    if (b > c)
        swap(b, c), swap(ord[2], ord[3]);
    if (a > b)
        swap(a, b), swap(ord[1], ord[2]);
    for (int i = 0; i < 4; i++)
        ordm1[ord[i]] = i;
    for (int i = 0; i < U.size(); i++)
    {
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
    }
    sol.resize(n);
    for (int i = 0; i < n; i++)
        sol[i] = 0;
    fs = false;
    for (int tc = 1; tc <= BB / (n + U.size()) and tc <= 1; tc++)
    {
        if (fs)
            break;
        for (int i = 0; i < n; i++)
            shuffle(g[i].begin(), g[i].end(), default_random_engine(rng()));
        int r = rng() % n;
        for (int i = 0; i < n; i++)
            viz[i] = false;
        h[r] = 0;
        dfs(r, -1);
        if (fs)
        {
            for (int i = 0; i < n; i++)
                sol[i] = 3;
            ct = cate;
            cd(sub, tat, col);
            ct = cate2;
            cd(r, -1, 3 - col);
        }
    }
    for (int i = 0; i < sol.size(); i++)
        sol[i] = ord[sol[i]];
    vector<int> fr(4);
    for (int i = 0; i < n; i++)
        fr[sol[i]]++;
    bool all0 = true;
    if (fr[1] + fr[2] + fr[3] > 0)
        all0 = false;
    assert(all0 or (fr[1] == A and fr[2] == B and fr[3] == C));
    return sol;
}

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