Submission #44661865

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)

typedef long long ll;
typedef __int128 lll;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef unsigned long long ull;

const int N = 1000010;
const int mod = 998244353;

int n, m, cnt, tot, a[N], b[N], fa[N], val[N], siz[N], head[N];
struct edge { int to, nxt; } e[N * 2]; int q, dep[N], f[N][20];

inline void add(int x, int y)
{
    e[++cnt] = {y, head[x]}, head[x] = cnt;
    e[++cnt] = {x, head[y]}, head[y] = cnt;
}

inline int gf(int x)
{
    return (fa[x] == x ? x : fa[x] = gf(fa[x]));
}

inline void dfs(int now, int fa)
{
    f[now][0] = fa, dep[now] = dep[fa] + 1;
    for(int i = 1;i <= 19;i++)
        f[now][i] = f[f[now][i - 1]][i - 1];
    for(int i = head[now];i;i = e[i].nxt)
        if(e[i].to != fa) dfs(e[i].to, now), siz[now] += siz[e[i].to];
    if(siz[now] == 0) siz[now]++;
}

inline int check(int x, int y, int z)
{
    for(int i = 19;i >= 0;i--)
        if(val[f[x][i]] <= z) x = f[x][i];
    for(int i = 19;i >= 0;i--)
        if(val[f[y][i]] <= z) y = f[y][i];
    return (x == y ? siz[x] : siz[x] + siz[y]);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m, val[0] = 1e9;
    iota(fa + 1, fa + n + 1, 1), tot = n;
    fro(i, 1, m) cin >> a[i] >> b[i];
    fro(i, 1, m)
    {
        int x = gf(a[i]), y = gf(b[i]);
        if(x == y) continue; val[++tot] = i;
        add(x, tot), add(y, tot);
        fa[x] = fa[y] = fa[tot] = tot;
    }
    dfs(tot, 0), cin >> q;
    fro(i, 1, q)
    {
        int x, y, z;
        cin >> x >> y >> z;
        int l = 1, r = 1e9, ans;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(check(x, y, mid) < z)
                l = mid + 1;
            else r = mid - 1, ans = mid;
        }
        cout << ans << "\n";
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:60:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   60 |         if(x == y) continue; val[++tot] = i;
      |         ^~
./Main.cpp:60:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   60 |         if(x == y) continue; val[++tot] = i;
      |                              ^~~
./Main.cpp:77:24: warning: ‘ans’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         cout << ans << "\n";
      |                        ^~~~

Judge Result