Submission #1067885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067885		becaido	Split the Attractions (IOI19_split)	C++17	40 / 100	67 ms	17876 KiB

split

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "split.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int n, m;
vector<int> adj[SIZE];
int ty[SIZE], cnt[3], id[3];

int to[SIZE];
int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool merge(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return 0;
    to[b] = a;
    return 1;
}

int w[SIZE], pa[SIZE];
void dfs(int pos, int fa) {
    w[pos] = 1;
    for (int np : adj[pos]) if (np != fa) {
        pa[np] = pos;
        dfs(np, pos);
        w[pos] += w[np];
    }
}
void dfs2(int pos, int fa, int cl) {
    if (cnt[cl]) {
        ty[pos] = id[cl];
        cnt[cl]--;
    } else {
        ty[pos] = id[2];
    }
    for (int np : adj[pos]) if (np != fa) dfs2(np, pos, cl);
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
    n = _n, m = p.size();
    FOR (i, 1, n) {
        ty[i] = 0;
        adj[i].clear();
    }
    iota(to + 1, to + n + 1, 1);
    FOR (i, 0, m - 1) {
        p[i]++, q[i]++;
        if (merge(p[i], q[i])) {
            adj[p[i]].pb(q[i]);
            adj[q[i]].pb(p[i]);
        }
    }

    cnt[0] = a, cnt[1] = b, cnt[2] = c;
    iota(id, id + 3, 0);
    sort(id, id + 3, [&](int i, int j) {
        return cnt[i] < cnt[j];
    });
    sort(cnt, cnt + 3);
    FOR (i, 0, 2) id[i]++;

    dfs(1, 1);
    FOR (i, 1, n) {
        if (cnt[0] <= w[i] && cnt[1] <= n - w[i]) {
            dfs2(i, pa[i], 0);
            dfs2(pa[i], i, 1);
            break;
        }
        if (cnt[1] <= w[i] && cnt[0] <= n - w[i]) {
            dfs2(i, pa[i], 1);
            dfs2(pa[i], i, 0);
            break;
        }
    }
    vector<int> ans;
    FOR (i, 1, n) ans.pb(ty[i]);
    return ans;
}

/*
in1
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
out1
1 1 3 1 2 2 3 1 3

in2
6 5
2 2 2
0 1
0 2
0 3
0 4
0 5
out2
0 0 0 0 0 0
*/

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