Submission #1123229

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

island

#include <bits/stdc++.h>

using namespace std;

namespace dsu_tree{
    const int MAX = 2e5 + 5;

    int lab[MAX], value[MAX], depth[MAX], used, timer_dfs, pos[MAX], rmq[20][MAX];
    vector<int> adj[MAX];

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

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

        adj[used].emplace_back(u);
        adj[used].emplace_back(v);
        value[used] = label;

        lab[u] = used;
        lab[v] = used;
        lab[used] = -1;
        ++used;
    }

    void dfs(int u){
        rmq[0][pos[u] = timer_dfs++] = u;
        for(auto v : adj[u]){
            depth[v] = depth[u] + 1;
            dfs(v);
            rmq[0][timer_dfs++]= u ;
        }
    }

    void init(int n){
        fill(lab, lab + n, -1);
        used = n;
        timer_dfs = 0;
    }

    void process(){
        dfs(used - 1);
        for(int i = 1; (1 << i) <= timer_dfs; ++i){
            for(int j = 0; j + (1 << i) <= timer_dfs; ++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_min(int u, int v){
        return value[get_lca(u, v)];
    }
}

namespace weighted_tree{
    const int MAX = 1e5 + 5;

    int depth[MAX], tin[MAX], tout[MAX], timer_dfs, timer_rmq, pos[MAX], rmq[20][MAX];
    vector<int> adj[MAX];

    void add_edge(int u, int v){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    void dfs(int u, int p){
        tin[u] = ++timer_dfs;
        rmq[0][pos[u] = timer_rmq++] = u;

        for(auto v : adj[u]) if(v != p){
            depth[v] = depth[u] + 1;
            dfs(v, u);
            rmq[0][timer_rmq++] = u;
        }

        tout[u] = timer_dfs;
    }

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

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

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

    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 disjoint_set_union{
    vector<int> lab;
    disjoint_set_union(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;
    }

    bool same_set(int u, int v){ return root(u) == root(v); }
    int size(int u){ return -lab[root(u)]; }
};


namespace Data{
    const int MAX = 1e5;
    int T = 566;
    vector<int> nodes[MAX];
    vector<int> answer[MAX];
}

using namespace Data;

namespace query_dsu{
    int lab[MAX], comps[MAX];

    void init(int n){
        fill(lab, lab + n, -1);
        fill(comps, comps + n, 0);
    }

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

    int assign(int u, int v){
        comps[u] = (1 << v);
    }

    bool join(int u, int v){
        u = root(u);
        v = root(v);
        assert(u != v);
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        comps[u] |= comps[v];
        return true;
    }

    bool meet(int u){
        u = root(u);
        return comps[u] == 3;
    }

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

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

    dsu_tree::init(N);

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

    dsu_tree::process();
    weighted_tree::process();

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

    vector<bool> vis(N, false);
    for(int i = 0; i < K; ++i){
        if((int)nodes[i].size() >= T){
            answer[i].resize(K, -1);
            fill(vis.begin(), vis.end(), false);
            vector<int> assignment(N, -1);
            priority_queue<pair<int, int>> pq;
            for(int u : nodes[i]){
                pq.push({M, u});
                assignment[u] = M;
            }

            while(!pq.empty()){
                int mn, u;
                tie(mn, u) = pq.top();
                pq.pop();
                if(vis[u]) continue;
                answer[i][F[u]] = max(answer[i][F[u]], mn);
                vis[u] = true;

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

    for(int i = 0; i < N; ++i){
        sort(nodes[i].begin(), nodes[i].end(), [&](int u, int v){
            return weighted_tree::tin[u] < weighted_tree::tin[v];
        });
    }

    query_dsu::init(N);
}

vector<int> merge_sort(const vector<int>& A, const vector<int>& B){
    vector<int> C;
    int i = 0, j = 0;
    while(i < (int)A.size() || j < (int)B.size()){
        if(i == (int)A.size()) C.emplace_back(B[j++]);
        else if(j == (int)B.size()) C.emplace_back(A[i++]);
        else if(weighted_tree::tin[A[i]] < weighted_tree::tin[B[j]]) C.emplace_back(A[i++]);
        else C.emplace_back(B[j++]);
    }
    return C;
}

int solve_vt(vector<int> A, vector<int> B){
    for(auto u : A) query_dsu::assign(u, 0);
    for(auto u : B) query_dsu::assign(u, 1);
    vector<int> v = merge_sort(A, B);
    int cur = (int)v.size();
    for(int i = 1; i < cur; ++i){
        v.emplace_back(weighted_tree::get_lca(v[i - 1], v[i]));
    }

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

    v.erase(unique(v.begin(), v.end()), v.end());
    stack<int> st;
    st.push(v[0]);
    vector<tuple<int, int, int>> edges;
    for(int i = 1; i < (int)v.size(); ++i){
        while(!weighted_tree::in_subtree(st.top(), v[i])) st.pop();
        edges.emplace_back(dsu_tree::get_min(st.top(), v[i]), st.top(), v[i]);
        st.push(v[i]);
    }

    sort(edges.rbegin(), edges.rend());
    int ans = -1;
    for(auto [w, u, v] : edges){
        query_dsu::join(u, v);
        if(query_dsu::meet(u)){
            ans = w;
            break;
        }
    }

    assert(ans != -1);
    for(auto u : v) query_dsu::reset(u);
    return ans;
}

int Separate(int A, int B){
    if((int)nodes[A].size() < (int)nodes[B].size()) swap(A, B);
    if(!answer[A].empty()) return answer[A][B];
    return solve_vt(nodes[A], nodes[B]);
}

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

    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

Compilation message (stderr)

island.cpp: In function 'int query_dsu::assign(int, int)':
island.cpp:166:5: warning: no return statement in function returning non-void [-Wreturn-type]
  166 |     }
      |     ^

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