Submission

Score: 100

User: kittipos

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

Language: cpp

Time: 0.145 second

Submitted On: 2026-03-19 10:11:31

#include <bits/stdc++.h>

using namespace std;

class DSU {
private:
  vector<int> parent;

public:
  DSU(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  int get_parent(int v) {
    if (parent[v] == v) {
      return v;
    }

    int p = get_parent(parent[v]);
    parent[v] = p;
    return p;
  }

  void merge(int a, int b) { parent[get_parent(b)] = get_parent(a); }
};

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, q;
  cin >> n >> m >> q;
  vector<tuple<int, int, int>> roads; // distance source and destination;
  roads.resize(m + 1);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    roads[i] = {c, a, b};
  }
  roads.push_back(make_tuple(numeric_limits<int>::max(), 0, 0));

  sort(roads.begin(), roads.end());

  vector<tuple<int, int, int, int>> queries;
  queries.resize(q);
  for (int i = 0; i < q; i++) {
    int a, b, k;
    cin >> a >> b >> k;
    queries[i] = {k, a, b, i};
  }
  sort(queries.begin(), queries.end());
  DSU dsu = DSU(n);

  vector<bool> ans;
  ans.resize(q);
  int joined_counter = 0;
  for (int i = 0; i < q; i++) {
    int capacity = get<0>(queries[i]);
    int start = get<1>(queries[i]);
    int destination = get<2>(queries[i]);
    while (get<0>(roads[joined_counter]) <= capacity) {
      dsu.merge(get<1>(roads[joined_counter]), get<2>(roads[joined_counter]));
      joined_counter++;
    }
    // cout << get<3>(queries[i]) << endl;
    if (dsu.get_parent(start) == dsu.get_parent(destination)) {
      ans[get<3>(queries[i])] = true;
    } else {
      ans[get<3>(queries[i])] = false;
    }
  }
  for (int i = 0; i < q; i++) {
    if (ans[i]) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }

  return 0;
}