Submission #1123048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123048		Zero_OP	Trip to the Galapagos Islands (FXCUP4_island)	C++20	31 / 100	5095 ms	61996 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXM = 3e5 + 5;
int T = 200;

struct disjoint_set{
    vector<int> lab;
    disjoint_set(int n) : lab(n, -1) {}

    int root(int u){
        return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
    }

    bool join(int u, int v){
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }
} dsu(0);

struct dsu_tree{
    vector<int> lab, depth, pos, value, tour;
    vector<vector<int>> adj, rmq;
    dsu_tree(int n) : lab(n, -1), rmq(), tour(), depth(n, 0), pos(n, 0), adj(n), value(n, -1) {}

    int root(int u){
        return lab[u] < 0 ? u : lab[u] = root(lab[u]);
    }

    void add_edge(int u, int v, int label){
        u = root(u);
        v = root(v);
        assert(u != v);

        lab.emplace_back(-1);
        depth.emplace_back(0);
        pos.emplace_back(0);
        value.emplace_back(label);
        adj.emplace_back();

        adj.back().push_back(u);
        adj.back().push_back(v);

        lab[u] = (int)lab.size() - 1;
        lab[v] = (int)lab.size() - 1;
    }

    void dfs(int u){
        pos[u] = (int)tour.size();
        tour.emplace_back(u);
        for(auto v : adj[u]){
            depth[v] = depth[u] + 1;
            dfs(v);
            tour.emplace_back(u);
        }
    }

    int combine(int u, int v){
        return depth[u] < depth[v] ? u : v;
    }

    void process(){
        int sz = (int)lab.size();
        dfs(sz - 1);
        sz = (int)tour.size();
        int L = 32 - __builtin_clz(sz);
        rmq.resize(L);
        rmq[0] = tour;
        for(int i = 1; i < L; ++i){
            rmq[i].resize(sz - (1 << i) + 1);
            for(int j = 0; j + (1 << i) <= sz; ++j){
                rmq[i][j] = combine(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int get_lca(int u, int v){
        u = pos[u];
        v = pos[v];
        if(u > v) swap(u, v);
        int k = 31 - __builtin_clz(v - u + 1);
        return combine(rmq[k][u], rmq[k][v - (1 << k) + 1]);
    }

    int get_label(int u, int v){
        return value[get_lca(u, v)];
    }

    int size() { return (int)lab.size(); }
} tr(0);

vector<int> computed_answer[MAXN];
vector<int> nodes[MAXN];

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
    int N = (int)F.size();
    int M = (int)S.size();

    for(int i = 0; i < N; ++i) nodes[F[i]].emplace_back(i);

    vector<vector<pair<int, int>>> adj(N);
    dsu = disjoint_set(N);
    tr = dsu_tree(N);
    for(int i = M - 1; i >= 0; --i){
        if(dsu.join(S[i], E[i])){
            adj[S[i]].emplace_back(E[i], i + 1);
            adj[E[i]].emplace_back(S[i], i + 1);
            tr.add_edge(S[i], E[i], i + 1);
        }
    }

    tr.process();
    assert(tr.size() == 2 * N - 1);

    function<void(int, vector<int>&)> solve_for = [&](int c, vector<int>& ans){
        vector<bool> deleted(N, false);
        priority_queue<pair<int, int>> pq;
        vector<int> min_weighted(N, -1);
        for(auto it : nodes[c]) {
            min_weighted[it] = M;
            pq.push({M, it});
        }

        while(!pq.empty()){
            int mn, u;
            tie(mn, u) = pq.top(); pq.pop();
            if(deleted[u]) continue;
            deleted[u] = true;
            min_weighted[u] = mn;
            for(auto [v, w] : adj[u]){
                if(!deleted[v]){
                    pq.push({min(mn, w), v});
                }
            }
        }

        for(int i = 0; i < N; ++i){
            assert(deleted[i]);
            ans[F[i]] = max(ans[F[i]], min_weighted[i]);
        }
    };

    for(int i = 0; i < K; ++i){
        assert(!nodes[i].empty());
        if((int)nodes[i].size() > T){
            computed_answer[i].resize(K);
            solve_for(i, computed_answer[i]);
        }
    }
}

int Separate(int A, int B){
    if((int)nodes[A].size() < (int)nodes[B].size()) swap(A, B);
    if((int)nodes[A].size() > T){
        return computed_answer[A][B];
    }

    int ans = -1;
    for(auto u : nodes[B]){
        for(auto v : nodes[A]){
            ans = max(ans, tr.get_label(u, v));
        }
    }
    return ans;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int N, M, K, Q;
    cin >> N >> M >> K >> Q;
    vector<int> F(N);
    for(int i = 0; i < N; ++i) cin >> F[i];
    vector<int> S(M), E(M);
    for(int i = 0; i < M; ++i) cin >> S[i] >> E[i];

    Init(K, F, S, E);

    while(Q--){
        int A, B;
        cin >> A >> B;
        cout << Separate(A, B) << '\n';
    }

    return 0;
}
#endif //LOCAL

• Subtask 1: 31 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30