Submission #1123237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123237		Zero_OP	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	89 ms	27816 KiB

island

#include <bits/stdc++.h>

using namespace std;

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

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{
    int used;
    vector<int> lab, depth, pos, value, tour;
    vector<vector<int>> adj, rmq;
    dsu_tree(int n) : lab(2 * n, -1), rmq(), tour(), depth(2 * n, 0), pos(2 * n, 0), adj(2 * n), value(2 * n, -1), used(n) {}

    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[used] = -1;
        value[used] = label;
        adj[used].emplace_back(u);
        adj[used].emplace_back(v);
        lab[u] = used;
        lab[v] = used;
        ++used;
    }

    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(){
        dfs(used - 1);
        int 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)used; }
} tr(0);

int N, depth[MAXN], tin[MAXN], tout[MAXN], timer_dfs, timer_rmq, pos[MAXN], rmq[20][MAXN * 2];
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;
    rmq[0][pos[u] = timer_rmq++] = u;
    for(auto [v, w] : adj[u]) if(v != p){
        depth[v] = depth[u] + 1;
        dfs(v, u);
        rmq[0][timer_rmq++] = u;
    }
    tout[u] = timer_dfs;
}

int combine(int u, int v){ return depth[u] < depth[v] ? u : v; }
void preprocessRMQ(){
    for(int i = 1; (1 << i) <= timer_rmq; ++i){
        for(int j = 0; j + (1 << i) <= timer_rmq; ++j){
            rmq[i][j] = combine(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
        }
    }
}

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

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

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;
    }
} 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);
        } else assert(false);
    }

    dfs(0, -1);
    preprocessRMQ();
    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> assignment(N, -1);
        for(auto it : nodes[c]) {
            assignment[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;
            ans[F[u]] = max(ans[F[u]], assignment[u]);

            for(auto [v, w] : adj[u]){
                if(!deleted[v] && assignment[v] < min(mn, w)){
                    assignment[v] = min(mn, w);
                    pq.push({assignment[v], v});
                }
            }
        }
    };

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

    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: 0 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30