Submission #1285689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285689		baotoan655	Split the Attractions (IOI19_split)	C++20	100 / 100	63 ms	18600 KiB

split

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 1e5 + 5;
int n, m;
pair<int, int> a[3];
vector<int> g[N];
int ans[N];
int sz[N];
int low[N], in[N];
int tim;
bool ok = false;
int lim;

void go(int u, int c) {
    if(ans[u] != 0 || lim == 0) return;
    --lim;
    ans[u] = c;
    for(int v : g[u]) {
        if(in[v] >= in[u]) go(v, c);
    }
}
int dfs(int u) {
    if(sz[u] != 0 || ok) return 0;
    sz[u] = 1;
    in[u] = low[u] = ++tim;
    int mx = 0;
    for (int v : g[u]) {
        int sus = dfs(v);
        mx = max(mx, sus);
        sz[u] += sus;
        low[u] = min(low[u], in[v]);
    }

    if(sz[u] >= a[0].first && mx < a[0].first) {
        int S = n - sz[u];
        for(int v : g[u]) {
            if(S >= a[0].first) break;
            if(in[v] < in[u] || low[v] >= in[u]) continue;
            S += sz[v];
            in[v] = 0;
        }
        ok = true;
        if(S >= a[0].first) {
            if(S < a[1].first) swap(a[0], a[1]);
            lim = a[0].first;
            go(u, a[0].second);
            memset(in, 0, sizeof in);
            lim = a[1].first;
            go(0, a[1].second);
            for(int i = 0; i < n; ++i) if(ans[i] == 0) ans[i] = a[2].second;
        }
    }
    return sz[u];
}
vector<int> find_split(int _n, int _a, int b, int c, vector<int> p, vector<int> q) {
    n = _n;
    m = p.size();
    a[0] = {_a, 1};
    a[1] = {b, 2};
    a[2] = {c, 3};
    sort(a, a + 3);
    for(int i = 0; i < m; ++i) {
        g[p[i]].emplace_back(q[i]);
        g[q[i]].emplace_back(p[i]);
    }
    dfs(0);
    vector<int> res(n);
    for(int i = 0; i < n; ++i) res[i] = ans[i];
    return res;
}
//int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
//
//    file("A") else file("task");
//
//    cin >> n >> m;
//    for(int i = 0; i < 3; ++i) {
//        cin >> a[i].first;
//        a[i].second = i + 1;
//    }
//    sort(a, a + 3);
//    for(int i = 1; i <= m; ++i) {
//        int u, v;
//        cin >> u >> v;
//        g[u].emplace_back(v);
//        g[v].emplace_back(u);
//    }
//    dfs(0);
//    for(int i = 0; i < n; ++i) cout << ans[i] << ' ';
//    return 0;
//}

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