Submission #1123096

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

island

#include <bits/stdc++.h>

using namespace std;

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

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);

int N, lift[20][MAXN], depth[MAXN], tin[MAXN], tout[MAXN], timer_dfs;
vector<pair<int, int>> adj[MAXN];
vector<int> computed_answer[MAXN];
vector<int> nodes[MAXN];

void dfs(int u, int p){
    tin[u] = ++timer_dfs;
    for(auto [v, w] : adj[u]) if(v != p){
        depth[v] = depth[u] + 1;
        lift[0][v] = u;
        for(int i = 1; (1 << i) <= depth[v]; ++i){
            lift[i][v] = lift[i - 1][lift[i - 1][v]];
        }

        dfs(v, u);
    }
    tout[u] = timer_dfs;
}

bool in_subtree(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int get_lca(int u, int v){
    if(in_subtree(u, v)) return u;
    if(in_subtree(v, u)) return v;
    for(int i = 31 - __builtin_clz(depth[u]); i >= 0; --i){
        if(depth[u] >= (1 << i) && !in_subtree(lift[i][u], v)){
            u = lift[i][u];
        }
    }
    return lift[0][u];
}

struct query_dsu{
    vector<int> lab;
    vector<vector<int>> cnt;
    query_dsu(int n) : lab(n, -1), cnt(n, vector<int>(3, 0)) {}

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

    bool unite(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;
        for(int i = 0; i < 3; ++i) cnt[u][i] += cnt[v][i];
        return true;
    }

    bool meet(int u){
        u = root(u);
        return cnt[u][1] && cnt[u][2];
    }

    void reset(int u){
        lab[u] = -1;
        cnt[u][0] = cnt[u][1] = cnt[u][2] = 0;
    }

    void debug(){
        cout << "debug query part : \n";
        for(int i = 0; i < (int)lab.size(); ++i){
            cout << lab[i] << ' ' << cnt[i][0] << ' ' << cnt[i][1] << ' ' << cnt[i][2] << '\n';
        }
        cout << '\n';
    }
} slv(0);

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);

    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);
        }
    }

    dfs(0, -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]);
        }
    }

    slv = query_dsu(N);
}

int solve_virtual_tree(vector<int> A, vector<int> B){
    vector<int> vert = A;
    vert.insert(vert.end(), B.begin(), B.end());

    sort(vert.begin(), vert.end(), [&](int u, int v){
        return tin[u] < tin[v];
    });

    vert.erase(unique(vert.begin(), vert.end()), vert.end());
    int cur = (int)vert.size();
    for(int i = 1; i < cur; ++i){
        vert.emplace_back(get_lca(vert[i - 1], vert[i]));
    }

    sort(vert.begin(), vert.end(), [&](int u, int v){
        return tin[u] < tin[v];
    });
    vert.erase(unique(vert.begin(), vert.end()), vert.end());

    for(auto u : vert){
        if(binary_search(A.begin(), A.end(), u)) slv.cnt[u][1] = 1;
        if(binary_search(B.begin(), B.end(), u)) slv.cnt[u][2] = 1;
    }

//    slv.debug();

    vector<tuple<int, int, int>> edges;

    stack<int> st;
    st.push(vert[0]);
    cur = (int)vert.size();
    for(int i = 1; i < cur; ++i){
        while(!in_subtree(st.top(), vert[i])){
            st.pop();
        }

        assert(!st.empty());
        edges.emplace_back(tr.get_label(st.top(), vert[i]), st.top(), vert[i]);
        st.push(vert[i]);
    }

    sort(edges.rbegin(), edges.rend());

    int ans = -1;
    for(auto [w, u, v] : edges){
        slv.unite(u, v);
        if(slv.meet(u)){
            ans = w;
            break;
        }
    }

    assert(ans != -1);
    for(auto u : vert){
        slv.reset(u);
    }

    return ans;
}

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];
    }

    return solve_virtual_tree(nodes[A], nodes[B]);
}

#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