Submission #680661

#	Time	Username	Problem	Language	Result	Execution time	Memory
680661		lohacho	Split the Attractions (IOI19_split)	C++14	100 / 100	209 ms	28008 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const int NS = (int)2e5 + 4;
int n;

struct Dsu{
    int n;
    vector<int> pr, rk;
    Dsu(int N):n(N){
        pr.resize(n), rk.resize(n);
        for(int i = 0; i < n; ++i) pr[i] = i, rk[i] = 1;
    }
    inline int get(int x){
        return x == pr[x] ? x : pr[x] = get(pr[x]);
    }
    inline bool unite(int x, int y){
        x = get(x), y = get(y);
        if(x != y){
            if(rk[x] < rk[y]) swap(x, y);
            pr[y] = x, rk[x] += rk[y];
            return true;
        }
        return false;
    }
};

int ca, cb, cc;
vector<int> way[NS], wayt[NS];
int sz[NS], ans[NS], need;
Dsu gr(NS + 4);

void cdfs(int x, int pr){
    for(auto&nxt:wayt[x]){
        if(nxt == pr){
            continue;
        }
        cdfs(nxt, x);
        sz[x] += sz[nxt];
    }
    sz[x] += 1;
}

void col(int x, int pr){
    for(auto&nxt:wayt[x]){
        if(nxt == pr){
            continue;
        }
        gr.unite(x, nxt);
        col(nxt, x);
    }
}

int cget(int x, int pr){
    for(auto&nxt:wayt[x]){
        if(nxt == pr){
            continue;
        }
        if(sz[nxt] > n / 2){
            return cget(nxt, x);
        }
    }
    return x;
}

void adfs(int x, int tcol){
    ans[x] = tcol; --need;
    for(auto&nxt:wayt[x]){
        if(!ans[nxt] && need){
            adfs(nxt, tcol);
        }
    }
}

vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> q) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    n = N;
    int m = (int)P.size();
    ca = 1, cb = 2, cc = 3;
    if(a > b) swap(a, b), swap(ca, cb);
    if(a > c) swap(a, c), swap(ca, cc);
    if(b > c) swap(b, c), swap(cb, cc);
    Dsu span(n + 4);
    for(int i = 1; i <= m; ++i){
        int x, y; x = P[i - 1], y = q[i - 1]; ++x, ++y;
        if(span.unite(x, y)){
            wayt[x].push_back(y), wayt[y].push_back(x);
        }
        else way[x].push_back(y), way[y].push_back(x);
    }
    cdfs(1, -1);
    int cent = cget(1, -1);
    multiset<pair<int, int>> st;
    for(auto&nxt:wayt[cent]){
        col(nxt, cent);
        st.insert({gr.rk[gr.get(nxt)], gr.get(nxt)});
    }
    for(int i = 1; i <= n; ++i){
        for(auto&nxt:way[i]){
            if(i == cent || nxt == cent){
                continue;
            }
            auto p = st.end(); --p;
            if(p->first >= a) break;
            int pi = gr.get(i), pnxt = gr.get(nxt);
            if(pi == pnxt) continue;
            wayt[i].push_back(nxt), wayt[nxt].push_back(i);
            auto si = st.find(make_pair(gr.rk[pi], pi));
            auto snxt = st.find(make_pair(gr.rk[pnxt], pnxt));
            gr.unite(pi, pnxt);
            st.insert(make_pair(gr.rk[gr.get(pi)], gr.get(pi)));
            st.erase(si), st.erase(snxt);
        }
    }
    auto p = st.end(); --p;
    if(p->first < a){
        return vector<int>(n, 0);
    }
    ans[cent] = cb;
    need = a;
    adfs(p->second, ca);
    need = b - 1;
    for(auto&nxt:wayt[cent]){
        if(!ans[nxt] && need){
            adfs(nxt, cb);
        }
    }
    for(int i = 1; i <= n; ++i){
        if(!ans[i]) ans[i] = cc;
    }

    vector<int> rv(n);
    for(int i = 0; i < n; ++i){
        rv[i] = ans[i + 1];
    }

    return rv;
}

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