Submission #295132

#	Time	Username	Problem	Language	Result	Execution time	Memory
295132		SamAnd	Split the Attractions (IOI19_split)	C++17	33 / 100	736 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;

int n, m;
vector<int> g[N];

int q[N];
int p0[N];
void dfs0(int x, int p)
{
    p0[x] = p;
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }
}

pair<int, int> u[4];

vector<int> ans;

void dfs(int x, int p, int y)
{
    if (ans[x - 1])
        return;
    if (!u[y].fi)
        return;
    ans[x - 1] = u[y].se;
    --u[y].fi;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs(h, x, y);
    }
}

vector<int> find_split(int N_, int A, int B, int C, vector<int> P, vector<int> Q)
{
    n = N_;
    m = sz(P);
    for (int i = 0; i < m; ++i)
    {
        int x = P[i];
        int y = Q[i];
        ++x;
        ++y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    u[1] = m_p(A, 1);
    u[2] = m_p(B, 2);
    u[3] = m_p(C, 3);
    sort(u + 1, u + 3 + 1);

    if (u[1].fi == 1)
    {
        ans.assign(n, 0);
        dfs(1, 1, 2);
        for (int x = 0; x < n; ++x)
        {
            if (!ans[x])
            {
                ans[x] = u[1].se;
                break;
            }
        }
        for (int x = 0; x < n; ++x)
        {
            if (!ans[x])
                ans[x] = u[3].se;
        }
        return ans;
    }

    if (m != n - 1)
    {
        g[P.back()].pop_back();
        g[Q.back()].pop_back();
    }

    dfs0(1, 1);
    for (int x = 1; x <= n; ++x)
    {
        if (u[1].fi <= min(q[x], n - q[x]) && u[2].fi <= max(q[x], n - q[x]))
        {
            ans.assign(n, 0);
            if (q[x] < n - q[x])
            {
                dfs(x, p0[x], 1);
                dfs(p0[x], x, 2);
            }
            else
            {
                dfs(x, p0[x], 2);
                dfs(p0[x], x, 1);
            }
            for (int i = 0; i < n; ++i)
            {
                if (!ans[i])
                    ans[i] = u[3].se;
            }
            return ans;
        }
    }
    ans.assign(n, 0);
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs0(int, int)':
split.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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