Submission #253651

#	Time	Username	Problem	Language	Result	Execution time	Memory
253651		HynDuf	Split the Attractions (IOI19_split)	C++14	18 / 100	135 ms	18040 KiB

split

#include "split.h"
#include <bits/stdc++.h>

#define task "SPLIT"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 2e5 + 3;
//int n, m, a, b, c;
int sz[N], eul[N], st[N], ed[N], neu, dep[N], par[N], id[4];
vi g[N], leaf[4];
ii A[4];
bool vis[N];
int team[N];
void dfs(int u)
{
    st[u] = ++neu;
    eul[neu] = u;
    vis[u] = 1;
    sz[u] = 1;
    for (int v : g[u]) if (!vis[v])
    {
        dep[v] = dep[u] + 1;
        dfs(v);
        sz[u] += sz[v];
    }
    ed[u] = neu;
}
void getleaves(int u, int teamid)
{
    vis[u] = 1;
    sz[u] = 1;
    for (int v : g[u]) if (!vis[v] && team[v] == teamid)
    {
        par[v] = u;
        getleaves(v, teamid);
        sz[u]++;
    }
    if (sz[u] == 1) leaf[teamid].eb(u);
}
void setteam(int teamid, int lim, int siz)
{
    int redun = siz - lim;
    rep(i, 1, redun)
    {
        //if (leaf[teamid].empty()) break;
        int cur = leaf[teamid].back();
        team[cur] = 3;
        leaf[teamid].pop_back();
        if (--sz[par[cur]] == 1) leaf[teamid].eb(par[cur]);

    }
}
bool canreach(int u, int mxd)
{
    rep(i, st[u], ed[u]) for (int v : g[eul[i]]) if (dep[v] < mxd) return 1;
    return 0;
}
vi find_split(int n, int a, int b, int c, vi p, vi q)
{
    vi ans(n, 0);
    //ios_base::sync_with_stdio(false); cin.tie(nullptr);
    //cin >> n >> m >> a >> b >> c;
    int m = SZ(p);
    rep(i, 1, m)
    {
        //int u, v;
        //cin >> u >> v;
        //u++, v++;
        int u = p[i - 1] + 1, v = q[i - 1] + 1;
        g[u].eb(v);
        g[v].eb(u);
    }
    A[0] = {a, 1};
    A[1] = {b, 2};
    A[2] = {c, 3};
    sort(A, A + 3);
    a = A[0].F; b = A[1].F;
    c = A[2].F;
    rep(i, 1, 3) id[i] = A[i - 1].S;
    dfs(1);
    int u = 0, mxd = -1;
    rep(i, 1, n) if (sz[i] >= a && mxd < dep[i])
    {
        mxd = dep[i];
        u = i;
    }
    if (n - sz[u] >= a)
    {
        int sz1 = sz[u], sz2 = n - sz[u];
        int rA = u, rB = 1;
        if (sz[u] >= b)
        {
            swap(rA, rB);
            swap(sz1, sz2);
            swap(id[1], id[2]);
            rep(i, st[u], ed[u]) team[eul[i]] = 2; // B-team
            rep(i, 1, n) if (team[i] == 0) team[i] = 1; // A-team
        }
        else
        {
            rep(i, st[u], ed[u]) team[eul[i]] = 1; // A-team
            rep(i, 1, n) if (team[i] == 0) team[i] = 2; // B-team
        }
        fill(vis, vis + 1 + n, 0);
        getleaves(rA, 1);
        getleaves(rB, 2);
        /*
        for (int l : leaf[1]) cout << l << ' ';
        cout << '\n';
        for (int l : leaf[2]) cout << l << ' ';
        cout << '\n';
        */
        setteam(1, a, sz1);
        setteam(2, b, sz2);
        rep(i, 1, n) ans[i - 1] = id[team[i]];
    } else
    {
        if (m == n - 1)
        {
            rep(i, 0, n - 1) ans[i] = 0;
            return ans;
        }
        int sz1 = sz[u];
        int sz2 = n - sz[u];
        rep(i, st[u], ed[u]) team[eul[i]] = 1; // A-team
        rep(i, 1, n) if (team[i] == 0) team[i] = 2; // B-team
        bool ok = 0;
        for (int v : g[u]) if (dep[v] > dep[u])
        {
            if (canreach(v, dep[u]))
            {
                rep(i, st[v], ed[v]) team[eul[i]] = 2;
                sz2 += sz[v];
                sz1 -= sz[v];
                if (sz2 >= a)
                {
                    ok = 1;
                    break;
                }
            }
        }
        if (!ok)
        {
            rep(i, 1, n) ans[i - 1] = 0;
            return ans;
        }
        int rA = u, rB = 1;
        if (sz1 >= sz2)
        {
            swap(rA, rB);
            swap(sz1, sz2);
            swap(id[1], id[2]);
            rep(i, 1, n) if (team[i] == 1) team[i] = 2;
            else team[i] = 1;
        }
        fill(vis, vis + 1 + n, 0);
        getleaves(rA, 1);
        getleaves(rB, 2);
        setteam(1, a, sz1);
        setteam(2, b, sz2);
        rep(i, 1, n) ans[i - 1] = id[team[i]];
    }
    return ans;
}
/*
int main()
{
    freopen("S.in", "r", stdin);
    //freopen("S.out", "w", stdout);
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;
    vi pp(m, 0), qq(m, 0);

    rep(i, 0, m - 1) cin >> pp[i] >> qq[i];
    vi res = find_split(n, a, b, c, pp, qq);
    for (int v : res) cout << v << ' ';

    return 0;
}
*/

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