Submission #1256270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256270		nerrrmin	Split the Attractions (IOI19_split)	C++20	0 / 100	3 ms	7492 KiB

split

#include "split.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int m, deg[maxn];
vector < int > g[maxn];
int used[maxn];
int sub[maxn], p[maxn], ver = 0, all;
int in, out;
int c1, c2, c3;
int col1, col2, col3;
void dfs(int beg, int from)
{
    used[beg] = 1;
    sub[beg] = 1;
    p[beg] = from;
    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        dfs(nb, beg);
        sub[beg] += sub[nb];
    }
    if(sub[beg] >= c1 && all-sub[beg] >= c1)
    {
        ver = beg;
        in = sub[beg];
        out = all-sub[beg];
    }
}


int track[maxn];

int broika;
void rec(int beg, int from, int cvqt)
{
    if(!broika)return;
    broika --;
    track[beg] = cvqt;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec(nb, beg, cvqt);

    }
}
int cnt = 0;
void rec2(int beg, int from, int cvqt)
{
    cnt ++;
    if(!broika)return;
    broika --;
    track[beg] = cvqt;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec2(nb, beg, cvqt);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    m = p.size();
    all = n;
    ver = -1;
    for (int i = 0; i < m; ++ i)
    {
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    if(a <= min(b, c))
    {
        c1 = a;
        col1 = 1;
    }
    else if(b <= min(a, c))
    {
        c1 = b;
        col1 = 2;
    }
    else if(c <= min(a, b))
    {
        c1 = c;
        col1 = 3;
    }

    if(a != c1 && a >= max(b, c))
    {
        c3 = a;
        col3 = 1;
    }
    else if(b != c1 && b >= max(a, c))
    {
        c3 = b;
        col3 = 2;
    }
    else if(c != c1 && c >= max(a, b))
    {
        c3 = c;
        col3 = 3;
    }

    col2 = 6 - col1 - col3;
    c2 = n - c1 - c3;
    assert(c1 + c2 + c3 == n);
    assert(col1 >= 1 && col1 <= 3);
    assert(col2 >= 1 && col2 <= 3);
    assert(col3 >= 1 && col3 <= 3);

    dfs(0, -1);
    vector < int > ans;
    if(ver == 1)
    {
        for (int i = 1; i <= n; ++ i)
            ans.pb(0);
        return ans;
    }
    int pos = ver;
    if(out >= c2)
    {
        broika = c1;
        rec(ver, p[pos], col1);
        broika = c2;
        rec2(p[pos], -1, col2);
        for (int j = 0; j < n; ++ j)
            if(track[j] == 0)track[j] = col3;

        for (int j = 0; j < n; ++ j)
            ans.pb(track[j]);
        return ans;
    }
    else
    {
         broika = c2;
        rec(ver, p[pos], col2);
        broika = c1;
        rec2(p[pos], -1, col1);
        for (int j = 0; j < n; ++ j)
            if(track[j] == 0)track[j] = col3;

        for (int j = 0; j < n; ++ j)
            ans.pb(track[j]);
        return ans;
    }

}

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