Submission #1256241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256241		nerrrmin	Split the Attractions (IOI19_split)	C++20	0 / 100	676 ms	1114112 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];
int half;
vector < int > g[maxn];
int used[maxn];
vector < int > path;
int isub[maxn];
void idfs(int beg, int from)
{
    isub[beg] = 1;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        idfs(nb, beg);
        isub[beg] += isub[nb];
    }
}
int find_centoid(int beg, int from)
{
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(isub[nb] > half)return find_centoid(nb, beg);
    }
    return beg;
}
int sub[maxn], par[maxn];
void dfs(int beg, int from)
{
    used[beg] = 1;
    sub[beg] = 1;
    path.pb(beg);
    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        dfs(nb, beg);
        sub[beg] += sub[nb];
    }
}

int c1, c2, c3;
int col1, col2, col3;
int track[maxn];
void rec(int beg, int from)
{
    if(!c1)return;
    c1 --;
    track[beg] = col1;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec(nb, beg);

    }
}
void rec2(int beg, int from)
{
    if(!c2)return;
    c2 --;
    track[beg] = col2;
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        if(track[nb])continue;
        rec2(nb, beg);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    m = p.size();
    half = n/2;
    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;
    }
    if(b <= min(a, c))
    {
        c1 = b;
        col1 = 2;
    }
    if(c <= min(a, b))
    {
        c1 = c;
        col1 = 3;
    }

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

    col2 = 6 - col1 - col3;
    c2 = n - c1 - c3;
    assert(col1 >= 1 && col1 <= 3);
    assert(col2 >= 1 && col2 <= 3);
    assert(col3 >= 1 && col3 <= 3);
    idfs(0, -1);
    int nc = find_centoid(0, -1);
    dfs(nc, -1);
    vector < int > ans;
    int mn = n, pos = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(sub[i] >= c1)
        {
            mn = min(mn, sub[i]);
            if(mn == sub[i])pos = i;

        }
    }
    int outside = n - mn;
    if(outside >= c2)
    {
        rec(pos, p[pos]);
            rec2(p[pos], -1);
            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;
    }
    for (int i = 0; i < n; ++ i)
        ans.pb(0);
    return ans;
}

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