Submission #1144022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144022		thangdz2k7	Split the Attractions (IOI19_split)	C++17	100 / 100	67 ms	24132 KiB

split

#include <bits/stdc++.h>
#define ALL(v) (v).begin(), (v).end()
#define pb push_back

using namespace std;

const int N = 1e5 + 5;

vector <pair <int, int>> type(3);
vector <int> adj[N], tree[N];
int st[N], ed[N], cnt = 0, sz[N], r;

int dfs(int u){
    st[u] = ++ cnt;
    sz[u] = 1;

    for (auto v : adj[u]){
        if (!st[v]){
            tree[u].pb(v);
            int k = dfs(v);
            sz[u] += sz[v];
            if (sz[v] >= type[0].first) return k;
        }
    }

    ed[u] = cnt;
    return u;

}

vector <int> ans;
int rc[N];

bool dfs2(int u){
    for (int v : tree[u]) if (dfs2(v)) return true;
    for (int v : adj[u]) if (ed[v] < st[r] || st[v] > ed[r]) return true;
    return false;
}

void ck(int u){
    rc[u] = 1;
    for (int v : tree[u]) ck(v);
}

void ass(int u, pair <int, int> &type){
    if (type.first){
        ans[u] = type.second;
        -- type.first;
    }
    for (int v : tree[u]) if (!rc[v] && type.first && !ans[v] && st[r] <= st[v] && ed[v] <= ed[r]) ass(v, type);
}

void ass1(int u, pair <int, int> &type){
    if (type.first){
        ans[u] = type.second;
        -- type.first;
    }
    for (int v : adj[u]) if (!ans[v] && type.first) ass1(v, type);
}

vector <int> find_split(int n, int a, int b, int c, vector <int> u, vector <int> v){
    ans.resize(n, 0);
    type[0] = {a, 1}, type[1] = {b, 2}, type[2] = {c, 3};
    sort(ALL(type));
    for (int i = 0; i < u.size(); ++ i) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
    r = dfs(0);
    int p1 = sz[r];
    int p2 = n - sz[r];

    for (int v : tree[r]){
        if (dfs2(v)){
            if (p1 - sz[v] >= type[0].first) {
                p1 -= sz[v];
                p2 += sz[v];
                ck(v);
            }
        }
    }

    if (p2 < type[0].first) return ans;
    if (p2 >= type[1].first){
        ass(r, type[0]);
        ass1(0, type[1]);
    }
    else {
        ass(r, type[1]);
        ass1(0, type[0]);
    }

    for (int i = 0; i < n; ++ i) if (!ans[i]) ans[i] = type[2].second;

    return ans;
}
//
//int main(){
//    int n, m; cin >> n >> m;
//    int a, b, c; cin >> a >> b >> c;
//    vector <int> u, v;
//    for (int i = 0; i < m; ++ i){
//        int z, k; cin >> z >> k;
//        u.pb(z);
//        v.pb(k);
//    }
//
//    for (int ans : find_split(n, a, b, c, u, v)) cout << ans << ' ';
//}

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