Submission #762483

#	Time	Username	Problem	Language	Result	Execution time	Memory
762483		boris_mihov	Split the Attractions (IOI19_split)	C++17	18 / 100	86 ms	32624 KiB

split

#include "split.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, m;
int aNum;
int bNum;
int cNum;
int timer;
int t[MAXN];
int sz[MAXN];
int low[MAXN];
bool vis[MAXN];
int comp[MAXN];
std::vector <int> g[MAXN];
std::vector <int> tree[MAXN];
std::vector <int> ans; 
int a, b, c;

void assignComponent(int node)
{
    comp[node] = 1;
    for (const int &u : tree[node])
    {
        assignComponent(u);
    }
}

bool dfs(int node, int par)
{
    sz[node] = 1;
    vis[node] = true;
    t[node] = low[node] = ++timer;

    int remove = 0;
    std::vector <int> removeAble;
    std::vector <int> mandatory;
    for (const int &u : g[node])
    {
        if (u == par)
        {
            continue;
        }

        if (vis[u])
        {
            low[node] = std::min(low[node], t[node]);
            continue;
        }

        tree[node].push_back(u);
        if (dfs(u, node))
        {
            return true;
        }
        
        sz[node] += sz[u];
        low[node] = std::min(low[node], low[u]);

        if (low[u] < t[node])
        {
            remove += sz[u];
            removeAble.push_back(u);
        } else
        {
            mandatory.push_back(u);
        }
    }

    if (sz[node] >= a && remove + n - sz[node] >= b)
    {
        comp[node] = 1;
        for (const int &u : removeAble)
        {
            if (sz[node] - sz[u] >= a)
            {
                sz[node] -= sz[u];
            } else
            {
                assignComponent(u);
            }
        }

        for (const int &u : mandatory)
        {
            assignComponent(u);
        }

        return true;
    }

    if (sz[node] >= b && remove + n - sz[node] >= a)
    {
        comp[node] = 1;
        for (const int &u : removeAble)
        {
            if (sz[node] - sz[u] >= b)
            {
                sz[node] -= sz[u];
            } else
            {
                assignComponent(u);
            }
        }

        for (const int &u : mandatory)
        {
            assignComponent(u);
        }

        return true;
    }

    return false;
}

int needed;
void cutComponents(int node)
{
    vis[node] = true;
    if (needed >= 1)
    {
        if (comp[node] == 1)
        {
            ans[node - 1] = aNum;
        } else
        {
            ans[node - 1] = bNum;
        }
    
        needed--;
    }

    for (const int &u : g[node])
    {
        if (!vis[u] && comp[node] == comp[u])
        {
            cutComponents(u);
        } 
    }
}

std::vector <int> find_split(int N, int A, int B, int C, std::vector <int> u, std::vector <int> v)
{   
    n = N;
    a = A;
    b = B;
    c = C;    
    aNum = 1;
    bNum = 2;
    cNum = 3;
    m = u.size();

    if (a > b)
    {
        std::swap(a, b);
        std::swap(aNum, bNum);
    }

    if (a > c)
    {
        std::swap(a, c);
        std::swap(aNum, cNum);
    }

    if (b > c)
    {
        std::swap(b, c);
        std::swap(bNum, cNum);
    }

    for (int i = 0 ; i < m ; ++i)
    {
        g[u[i] + 1].push_back(v[i] + 1);
        g[v[i] + 1].push_back(u[i] + 1);
    }

    ans.resize(n, 0);
    bool res = dfs(1, 0);
    if (!res)
    {
        return ans;
    }

    std::fill(vis + 1, vis + 1 + n, false);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (vis[i])
        {
            continue;
        }

        if (comp[i] == 1) needed = a;
        else needed = b;
        cutComponents(i);
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (ans[i] == 0)
        {
            ans[i] = cNum;
        }
    }

    return ans;
}

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