Submission

Score: 100

User: mantaggez

Problemset: เดินทางข้ามชุมชน

Language: cpp

Time: 0.208 second

Submitted On: 2025-12-07 13:10:37

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

int n, m, q;

int fnd(int cur, vector<int> &par) {
    if (par[cur] == cur) return cur;
    return par[cur] = fnd(par[cur], par);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;

    vector<pair<int, pair<int, pair<int,int>>>> g;
    g.reserve(m + q);

    // edges
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.push_back({w, {0, {u, v}}});   // idx = 0 means edge
    }

    // queries
    for (int i = 0; i < q; i++) {
        int a, b, k;
        cin >> a >> b >> k;
        g.push_back({k, {i+1, {a, b}}}); // idx = query id
    }

    // custom sort: sort by w, but edges (idx=0) must come before queries (idx>0)
    sort(g.begin(), g.end(),
        [](auto &A, auto &B) {
            if (A.first != B.first) return A.first < B.first;
            return A.second.first < B.second.first; // edges first
        });

    // DSU size must be n, NOT n+1 (nodes are 0..n-1)
    vector<int> par(n);
    iota(par.begin(), par.end(), 0);

    vector<bool> ans(q+1, false);

    // process
    for (auto &x : g) {
        int w = x.first;
        int idx = x.second.first;             // 0 = edge, >0 = query
        int u = x.second.second.first;
        int v = x.second.second.second;

        if (idx == 0) {
            // edge
            int a = fnd(u, par);
            int b = fnd(v, par);
            if (a != b) par[a] = b;
        } else {
            // query
            ans[idx] = (fnd(u, par) == fnd(v, par));
        }
    }

    // output in required format ("Yes" / "No")
    for (int i = 1; i <= q; i++) {
        cout << (ans[i] ? "Yes\n" : "No\n");
    }
}