Submission #74522132

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int n, m, f[200010];
inline int fnd(int x){return x == f[x]? x : f[x] = fnd(f[x]);}
int fa[200010], w[200010], kf[20][200010], d[200010], sz[200010];
int lca(int u, int v){
    if (d[u] < d[v])swap(u, v);
    for (int k = d[u] - d[v], i = 0; k >> i; ++i)
        if (k >> i & 1)u = kf[i][u];
    if (u == v)return u;
    for (int i = __lg(n); ~i; --i)
        if (kf[i][u] ^ kf[i][v])u = kf[i][u], v = kf[i][v];
    return fa[u];
}
constexpr int inf = 1e9+10;
inline int fd(int u, int mxw){
    for (int i = __lg(d[u]); ~i; --i)
        if (w[kf[i][u]] <= mxw)u = kf[i][u];
    return u;
}
int cal(int u, int v, int mxw){
    const int l = lca(u, v);
    if (w[l] <= mxw)return sz[fd(l, mxw)];
    return sz[fd(u, mxw)] + sz[fd(v, mxw)];
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    vector<tuple<int, int, int> > V;
    for (int i = 1, u, v; i <= m; ++i){
        cin >> u >> v;
        V.emplace_back(i, u, v);
    }
    sort(V.begin(), V.end());
    iota(f + 1, f + n + n + 1, 1);
    int tot = n;
    fill_n(sz + 1, n, 1);
    for (auto [w, u, v] : V){
        u = fnd(u), v = fnd(v);
        if (u == v)continue;
        fa[u] = fa[v] = ++tot;
        f[u] = f[v] = tot;
        ::w[tot] = w;
        sz[tot] = sz[u] + sz[v];
    }
    copy_n(fa + 1, tot, kf[0] + 1);
    for (int i = 1; 1 << i <= tot; ++i)
        for (int j = 1; j <= tot; ++j)
            kf[i][j] = kf[i - 1][kf[i - 1][j]];
    for (int i = tot - 1; i; --i)d[i] = d[fa[i]] + 1;
    w[0] = inf;
    int q;
    cin >> q;
    while (q--){
        int u, v, c;
        cin >> u >> v >> c;
        int L = 0, R = inf, rs = -1;
        while (L <= R){
            int M = L + R >> 1;
            if (cal(u, v, M) >= c)rs = M, R = M - 1;
            else L = M + 1;
        }
        cout << rs << "\n";
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:59:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             int M = L + R >> 1;
      |                     ~~^~~

Judge Result