Submission #1283895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283895		zNatsumi	Split the Attractions (IOI19_split)	C++20	18 / 100	77 ms	26096 KiB

split

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, a, b, c, num[N], low[N], sz[N], timer, mid, ans[N], cnt[4];
vector<int> ad[N], child[N];
vector<array<int, 2>> vt;

void dfs(int u, int p = -1){
    num[u] = low[u] = ++timer;
    sz[u] = 1;

    for(auto v : ad[u]) if(v != p){
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            dfs(v, u);
            sz[u] += sz[v];
            low[u] = min(low[u], low[v]);
            child[u].push_back(v);
        }
    }

    int inSz = sz[u], outSz = n - sz[u];

    for(auto v : child[u]){
        if(outSz >= vt[0][0]) break;
        if(low[v] < num[u] && inSz - sz[v] >= vt[0][0]){
            inSz -= sz[v];
            outSz += sz[v];
        }
    }

    if(inSz >= vt[0][0] && outSz >= vt[0][0]) mid = u;
}

void color(int u, int c){
    if(cnt[c]){
        cnt[c] -= 1;
        ans[u] = c;
    }
    if(!cnt[c]) return;

    for(auto v : child[u]){
        color(v, c);
    }
}

void color2(int u, int c){
    if(cnt[c]){
        cnt[c] -= 1;
        ans[u] = c;
    }
    if(!cnt[c]) return;

    for(auto v : ad[u]) if(!ans[v]){
        color2(v, c);
    }
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){
    n = _n; a = _a; b = _b, c = _c;
    m = _p.size();

    vt = {{a, 1}, {b, 2}, {c, 3}};
    sort(vt.begin(), vt.end());

    for(int i = 0; i < m; ++i){
        ad[_p[i]].push_back(_q[i]);
        ad[_q[i]].push_back(_p[i]);
    }

    dfs(0, -1);

    if(mid == -1){
        vector<int> res(n, 0);
        return res;
    }
    cerr << mid << "\n";

    vector<int> p;

    int inSz = sz[mid], outSz = n - inSz;
    for(auto v : child[mid]){
        if(outSz >= vt[0][0]){
            p.push_back(v);
            continue;
        }
        if(low[v] < num[mid] && inSz - sz[v] >= vt[0][0]){
            inSz -= sz[v];
            outSz += sz[v];
        }
    }
    if(inSz < outSz){
        cnt[vt[0][1]] = vt[0][0] - 1; ans[mid] = vt[0][1];
        cnt[vt[1][1]] = vt[1][0];

        for(auto v : p) color(v, vt[0][1]);
        color2(0, vt[1][1]);
    }else{
        cnt[vt[1][1]] = vt[1][0] - 1; ans[mid] = vt[1][1];
        cnt[vt[0][1]] = vt[0][0];

        for(auto v : p) color(v, vt[1][1]);
        color2(0, vt[0][1]);
    }
    for(int i = 0; i < n; ++i) if(!ans[i]) ans[i] = vt[2][1];

    vector<int> res;
    for(int i = 0; i < n; ++i) res.push_back(ans[i]);
    return res;
}

#ifdef znatsumi
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    #define task "test"
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    int _n, _m, _a, _b, _c;
    cin >> _n >> _m >> _a >> _b >> _c;

    vector<int> _p(_m), _q(_m);
    for(int i = 0; i < _m; ++i) cin >> _p[i] >> _q[i];

    auto res = find_split(_n, _a, _b, _c, _p, _q);
    for(auto x : res) cout << x << " ";

    return 0;
}
#endif

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