fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define LL long long
  6.  
  7. struct universe {
  8.     vector<int> cha, rank;
  9.     universe(int n): cha(n + 1), rank(n + 1, 0) {
  10.         for (int i=1; i<=n; i++) cha[i] = i;
  11.     }
  12.     int find(int u) {
  13.         if (cha[u] != u) cha[u] = find(cha[u]);
  14.         return cha[u];
  15.     }
  16.     bool join(int u, int v) {
  17.         u = find(u), v = find(v);
  18.         if (u == v) return false;
  19.         if (rank[u] == rank[v]) rank[u]++;
  20.         if (rank[u] > rank[v]) cha[v] = u;
  21.         else cha[u] = v;
  22.         return true;
  23.     }
  24. };
  25.  
  26. struct pack { int u, v; };
  27.  
  28. int main() {
  29.     ios::sync_with_stdio(false); cin.tie(0);
  30.     int T; cin >> T;
  31.     while (T--) {
  32.         int n, m, Q; cin >> n >> m >> Q;
  33.         vector<pack> e(m);
  34.         vector<int> w(m);
  35.         for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
  36.         while (Q--) {
  37.             int id; cin >> id; id--;
  38.             int s; cin >> s;
  39.             vector<int> ww(w);
  40.             while (s--) {
  41.                 int t, w; cin >> t >> w;
  42.                 ww[t-1] = w;
  43.             }
  44.             universe a(n);
  45.             for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
  46.                 a.join(e[i].u, e[i].v);
  47.             }
  48.             if (a.join(e[id].u, e[id].v)) cout << "NO\n";
  49.             else cout << "YES\n";
  50.         }
  51.     }
  52.     return 0;
  53. }
Runtime error #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XeH8jp
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!