Submission #480545

#	Time	Username	Problem	Language	Result	Execution time	Memory
480545		couplefire	Split the Attractions (IOI19_split)	C++17	100 / 100	154 ms	40780 KiB

split

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

const int N = 200005;

int n, m, k, id[N], siz[N], rt;
vector<int> adj[N], tadj[N], nadj[N], comps[N], orda;
vector<pair<int, int>> bruh;
bool vis[N];

void get_tree(int v){
    vis[v] = 1; siz[v] = 1;
    for(auto u : adj[v])
        if(!vis[u]) tadj[v].push_back(u), tadj[u].push_back(v), get_tree(u), siz[v] += siz[u];
}

int get_centroid(){
    int p = -1, v = 0;
    do{
        int nxt = -1;
        for(auto u : tadj[v])
            if(u!=p && 2*siz[u]>n) nxt = u;
        p = v, v = nxt;
    } while(~v);
    return p;
}

void get_label(int v, int p, int idx){
    comps[idx].push_back(v);
    id[v] = idx;
    for(auto u : tadj[v])
        if(u!=p) get_label(u, v, idx);
}

void get_orda(int v){
    vis[v] = 1;
    orda.push_back(v);
    for(auto u : adj[v])
        if(!vis[u]) get_orda(u);
}

vector<int> get_ans(vector<int> a0){
    memset(vis, 0, sizeof vis);
    for(auto x : a0) vis[x] = 1;
    for(int i = 0; i<n; ++i)
        if(!vis[i]){get_orda(i); break;}
    vector<int> ans(n, bruh[2].second);
    while((int)a0.size()>bruh[0].first) orda.push_back(a0.back()), a0.pop_back();
    for(auto x : a0)
        ans[x] = bruh[0].second;
    for(int i = 0; i<bruh[1].first; ++i)
        ans[orda[i]] = bruh[1].second;
    return ans;
}

bool find_good(int v, int& cur){
    vis[v] = 1; cur += comps[v].size();
    orda.push_back(v);
    if(cur>=bruh[0].first) return 1;
    for(auto u : nadj[v])
        if(!vis[u]){
            bool tmp = find_good(u, cur);
            if(tmp) return 1;
        }
    return 0;
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){
    n = _n, m = _p.size();
    bruh.push_back({_a, 1});
    bruh.push_back({_b, 2});
    bruh.push_back({_c, 3});
    sort(bruh.begin(), bruh.end());
    for(int i = 0; i<m; ++i)
        adj[_p[i]].push_back(_q[i]), adj[_q[i]].push_back(_p[i]);
    get_tree(0);
    rt = get_centroid(); k = tadj[rt].size();
    for(int i = 0; i<k; ++i)
        get_label(tadj[rt][i], rt, i);
    id[rt] = -1;
    for(int i = 0; i<k; ++i)
        if((int)comps[i].size()>=bruh[0].first)
            return get_ans(comps[i]);
    for(int i = 0; i<m; ++i){
        int u = id[_p[i]], v = id[_q[i]];
        if(u==v || u==-1 || v==-1) continue;
        nadj[u].push_back(v);
        nadj[v].push_back(u);
    } memset(vis, 0, sizeof vis);
    for(int i = 0; i<k; ++i){
        if(vis[i]) continue;
        int tot = 0;
        if(find_good(i, tot)){
            vector<int> a0;
            for(auto x : orda)
                a0.insert(a0.end(), comps[x].begin(), comps[x].end());
            orda.clear(); return get_ans(a0);
        } else{
            orda.clear();
        }
    }
    vector<int> ans(n, 0);
    return ans;
}

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