Submission #1305219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305219		andrei_iorgulescu	Split the Attractions (IOI19_split)	C++20	100 / 100	98 ms	33992 KiB

split

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

using namespace std;

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

const int BB = 5e7;

int n, a, b, c;
vector<int> g[100005];
vector<int> f[100005];
vector<int> be[100005], fe[100005];
bool viz[100005];
int t[100005];
int sz[100005];
int h[100005];
vector<int> sol;

void dfs(int nod)
{
    viz[nod] = true;
    sz[nod] = 1;
    for (auto fiu : g[nod])
    {
        if (!viz[fiu])
        {
            t[fiu] = nod;
            h[fiu] = 1 + h[nod];
            f[nod].push_back(fiu);
            dfs(fiu);
            sz[nod] += sz[fiu];
        }
        else if (fiu != t[nod])
        {
            be[nod].push_back(fiu);
            fe[fiu].push_back(nod);
        }
    }
}

vector<int> subarb;

void gs(int nod)
{
    subarb.push_back(nod);
    for (auto fiu : f[nod])
        gs(fiu);
}

void get_subarb(int nod)
{
    subarb.clear();
    gs(nod);
}

int ct;

void bro(int nod, int cl, int blk)
{
    if (ct == 0)
        return;
    sol[nod] = cl;
    ct--;
    for (auto fiu : f[nod])
        if (fiu != blk)
            bro(fiu, cl, blk);
}

void fin(int r, int fiu)
{
    //cout << r << ' ' << fiu << endl;
    for (int i = 0; i < n; i++)
        sol[i] = 3;
    if (sz[fiu] < b)
    {
        int cl;
        cl = 1, ct = a;
        bro(fiu, cl, -1);
        cl = 2, ct = b;
        bro(0, cl, fiu);
    }
    else
    {
        int cl;
        cl = 2, ct = b;
        bro(fiu, cl, -1);
        cl = 1, ct = a;
        bro(0, cl, fiu);
    }
}

void fin2(int r, vector<int> cine, vector<int> cine2)
{
    /*for (auto it : cine)
        cout << it << ' ';
    cout << endl;
    for (auto it : cine2)
        cout << it << ' ';
    cout << endl;*/
    int suma = n - sz[r];
    for (auto it : cine)
        suma += sz[it];
    for (int i = 0; i < n; i++)
        sol[i] = 3;
    if (suma < b)
    {
        int cl;
        cl = 1, ct = a;
        bro(0, cl, r);
        for (auto fiu : cine)
            bro(fiu, cl, -1);
        cl = 2, ct = b;
        sol[r] = 2;
        ct--;
        for (auto fiu : cine2)
            bro(fiu, cl, -1);
    }
    else
    {
        int cl;
        cl = 2, ct = b;
        bro(0, cl, r);
        for (auto fiu : cine)
            bro(fiu, cl, -1);
        cl = 1, ct = a;
        sol[r] = 1;
        ct--;
        for (auto fiu : cine2)
            bro(fiu, cl, -1);
    }
}

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;
    dfs(0);
    int r = 0;
    while (true)
    {
        int fu = -1;
        for (auto fiu : f[r])
            if (sz[fiu] > n - a)
                fu = fiu;
        if (fu == -1)
            break;
        r = fu;
    }
    int coef = n - sz[r];
    bool gata = false;
    for (auto fiu : f[r])
    {
        if (sz[fiu] >= a)
        {
            fin(r, fiu);
            gata = true;
            break;
        }
    }
    if (!gata)
    {
        vector<int> cine, cine2;
        for (auto fiu : f[r])
        {
            //cout << "ya" << endl;
            bool con = false;
            get_subarb(fiu);
            for (auto it : subarb)
                for (auto itt : be[it])
                    if (h[itt] < h[r])
                        con = true;
            if (con and coef < a)
            {
                cine.push_back(fiu);
                coef += sz[fiu];
            }
            else
                cine2.push_back(fiu);
        }
        if (coef >= a)
            fin2(r, cine, cine2);
        else
        {
            for (int i = 0; i < n; i++)
                sol[i] = 0;
        }
    }
    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: 24 / 24
• Subtask 5: 36 / 36