Submission #951180

#	Time	Username	Problem	Language	Result	Execution time	Memory
951180		thieunguyenhuy	Split the Attractions (IOI19_split)	C++17	100 / 100	91 ms	50740 KiB

split

#include <bits/stdc++.h>
using namespace std;

#define popcount(n) __builtin_popcountll((n))
#define clz(n) __builtin_clzll((n))
#define ctz(n) __builtin_ctzll((n))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

int n, m, root = 1, bucket = 0, dfs_cnt = 0;
int sz[N], color[N], par[N], dep[N], low[N], num[N], back[N];
vector<int> adj[N], ans;
pii a, b, c;

void get_ans() {
    for (int i = 1; i <= n; ++i)
    	if (!color[i]) ans[i - 1] = c.se;
    	else ans[i - 1] = color[i];
}

void color_subtree(int u, int c) {
    if (!color[u] && bucket > 0) color[u] = c, --bucket;
    else return;
    for (auto v : adj[u]) {
        if (num[v] > num[u] && !color[v] && bucket > 0) {
            color_subtree(v, c);
        }
    }
}

void color_random(int u, int c) {
    if (!color[u] && bucket > 0) color[u] = c, --bucket;
    else return;
    for (auto v : adj[u]) {
        if (!color[v] && bucket > 0) {
            color_random(v, c);
        }
    }
}

void dfs(int u) {
    sz[u] = 1; low[u] = num[u] = ++dfs_cnt; back[u] = u;
    for (auto v : adj[u]) {
        if (!num[v]) {
            par[v] = u; dfs(v); sz[u] += sz[v];
            minimize(low[u], low[v]);
            if (num[back[v]] < num[back[u]]) back[u] = back[v];
        }
        else if (v != par[u]) {
            minimize(low[u], num[v]);
            if (num[v] < num[back[u]]) back[u] = v;
        }
    }
}

bool check(int u) {
    if (sz[u] < a.fi) return false;
    for (auto v : adj[u])
        if (num[v] > num[u] && sz[v] >= a.fi) return false;
    return true;
}

void attempt(int u) {
    if (n - sz[u] >= a.fi) {
        if (sz[u] > n - sz[u]) swap(a, b);
        bucket = a.fi; color_subtree(u, a.se); 
        bucket = b.fi; color_subtree(root, b.se);
        get_ans();
        return;
    }
    
    vector<int> ve; int szU = sz[u];
    for (auto v : adj[u]) {
        if (num[v] > num[u] && low[v] < num[u]) {
            ve.emplace_back(v); szU -= sz[v];
            if (n - szU >= a.fi) break;
        }
    }
    if (n - szU < a.fi) return;
    if (szU > n - szU) swap(a, b);
    bucket = b.fi; for (auto v : ve) color_subtree(v, b.se); int save = bucket;
    bucket = a.fi; color_subtree(u, a.se); 
    bucket = save; for (auto v : ve) color_random(back[v], b.se);
    get_ans();
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n, a.fi = _a, b.fi = _b, c.fi = _c;
	ans.assign(n, 0);
    a.se = 1, b.se = 2, c.se = 3;

    if (a.fi > b.fi) swap(a, b);
    if (a.fi > c.fi) swap(a, c);
    if (b.fi > c.fi) swap(b, c);

    for (int i = 1; i <= n; ++i)
    	adj[i].clear();

    int m = p.size();
    for (int i = 0; i < m; ++i) {
        int u = p[i], v = q[i];
        ++u, ++v;
        adj[u].emplace_back(v), adj[v].emplace_back(u);
    }
    
    // Sắp xếp lại a, b, c tăng dần kèm theo màu tương ứng
    // Thực hiện dfs từ root bất kì
    // Gọi 1 cây con là vừa đủ khi size >= a và các cây con của nó có size < a
    // Gọi u là 1 cây con vừa đủ bất kì (dễ thấy luôn tồn tại u với mọi root (u = root))
    
    // Ta chứng minh nếu n - sz(u) >= a thì tồn tại đáp án, hay trong sz(u) hoặc n - sz(u) có ít nhất 1 thằng >= b
    // Giả sử sz(u) < b và n - sz(u) < b => sz(u) + (n - sz(u)) < b + b
    // => n < 2b => a + b + c < 2b => a + c < b: vô lí do a <= b <= c
    // Như vậy nếu n - sz(u) >= a thì ta có đáp án. Chỉ cần tô màu phần ít đỉnh hơn màu của a, còn lại màu của b
    // Nếu n - sz(u) < a, ta tìm các cây con của u có cung ngược lên trên, hay có low[v] < num[u]
    // Sau đó ta cắt cây con gốc v nối với đỉnh trên cung ngược của v
    
    // Ta chứng minh sau khi cắt như vậy sz(u) vẫn >= a
    // Giả sử sau khi cắt sz(u) < a hay sz(u) - sz(v) < a
    // Do u là cây con vừa đủ nên sz(v) < a. Lại có n - sz(u) < a
    // Cộng 3 vế ta có (sz(u) - sz(v)) + sz(v) + (n - sz(u)) < 3a
    // Hay n < 3a => a + b + c < 3a => b + c < 2a: vô lí do a <= b <= c
    // Như vậy nếu sz(u) >= a thì sau khi cắt cây con gốc v sz(u) vẫn >= a
    // Như vậy chỉ cần chọn các v đến khi không chọn được nữa hoặc n - sz(u) đã đủ thì thôi
    
    // Giờ ta sẽ đi chứng minh vì sao chọn u trong các cây con vừa đủ bất kì lại được?
    // Ta sẽ chứng minh tồn tại duy nhất 1 u sao cho n - sz(u) < a. Các trường hợp còn lại dễ thấy là đúng
    // Do n - sz(u) < a => a + b + c - sz(u) < a => b + c - sz(u) < 0 => sz(u) > b + c
    // Giả sử tồn tại cây con vừa đủ gốc x != u mà n - sz(x) < a => sz(x) > b + c
    // Gọi p = lca(u, x). Do u, x đều là cây con vừa đủ nên p != u và p != x
    // Khi đó dễ thấy sz(p) >= sz(u) + sz(x) > 2(b + c) > a + b + c = n: vô lí
    // Do đó tồn tại duy nhất 1 cây con gốc u có n - sz(u) < a

    // Ta đi chứng minh cây con gốc u trên vẫn cho ra kết quả đúng
    // Nếu sau khi cắt các cây con v của u có cung ngược lên trên mà vẫn không đủ
    // Thì bài toán không có đáp án
    // Bởi nếu tô u màu của c, dễ thấy các cây con còn lại của u sẽ coi như bỏ (do có size < a) => Loại
    // Nếu tô u màu của a, tương tự các cây con còn lại của u coi như bỏ => Loại
    // Nếu tô u màu của b, khi đó các cây con của u không thể có màu của a (do size < a)
    // Nên khi đó các cây con của u chỉ có thể có màu của b hoặc c
    // Khi đó sẽ không tô đủ màu của a do phần còn lại không đủ
    // Còn nếu sau khi cắt mà đủ thì ta tìm được đáp án

    dfs(root); pii best(inf, 0);
    for (int u = 1; u <= n; ++u)
        if (sz[u] >= a.fi) minimize(best, make_pair(sz[u], u));

    attempt(best.se);
	return ans;
}

#ifdef hwe
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n = 9, a = 4, b = 2, c = 3;
    vector<int> p = {0, 0, 0, 0, 0, 0, 1, 3, 4, 5};
    vector<int> q = {1, 2, 3, 4, 6, 8, 7, 7, 5, 6};

    vector<int> split = find_split(n, a, b, c, p, q);
    for (auto &x : split) cout << x << ' ';

    cerr << '\n'; return 0;
}
#endif

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