Submission #762537

#	Time	Username	Problem	Language	Result	Execution time	Memory
762537		boris_mihov	Split the Attractions (IOI19_split)	C++17	100 / 100	483 ms	48044 KiB

split

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

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::multiset <std::pair <int,int>> ms;
std::vector <int> g[MAXN];
std::vector <int> tree[MAXN];
std::vector <int> ans; 
int a, b, c;

void reset()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        tree[i].clear();
        low[i] = t[i] = sz[i] = vis[i] = comp[i] = false;
    }
}

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

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;
    bool shouldTry = true;
    bool isThere = false;
    bool loners = true;

    for (const int &u : g[node])
    {
        if (u == par)
        {
            continue;
        }

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

        tree[node].push_back(u);
        if (dfs(u, node))
        {
            return true;
        }
        
        if (sz[u] >= a)
        {
            shouldTry = false;
        }

        sz[node] += sz[u];
        low[node] = std::min(low[node], low[u]);

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

    if (sz[node] < a || !shouldTry)
    {
        return false;
    }

    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, 1);
            }
        }

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

        return true;
    }

    assert(sz[node] >= b);
    if (remove + n - sz[node] >= a)
    {
        std::fill(comp + 1, comp + 1 + n, 1);
        comp[node] = 0;

        for (const int &u : removeAble)
        {
            if (sz[node] - sz[u] >= b)
            {
                sz[node] -= sz[u];
            } else
            {
                assignComponent(u, 0);
            }
        }

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

        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::mt19937 mt(420);
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)
    {
        assert(!ms.count({u[i], v[i]}));
        g[u[i] + 1].push_back(v[i] + 1);
        g[v[i] + 1].push_back(u[i] + 1);
        ms.insert({u[i], v[i]});
        ms.insert({v[i], u[i]});
    }

    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;
}

Compilation message (stderr)

split.cpp: In function 'void reset()':
split.cpp:35:50: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |         low[i] = t[i] = sz[i] = vis[i] = comp[i] = false;
      |                                          ~~~~~~~~^~~~~~~
split.cpp: In function 'bool dfs(int, int)':
split.cpp:59:10: warning: unused variable 'loners' [-Wunused-variable]
   59 |     bool loners = true;
      |          ^~~~~~

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