fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pb push_back
  5.  
  6. const int MAXN = 1e5 + 15;
  7. const int oo   = 1e18;
  8. const int MOD  = 1e9 + 7;
  9.  
  10. struct Edge {
  11.      int u, v, w;
  12. } B[MAXN];
  13.  
  14. struct cmp {
  15.     bool operator() (Edge a, Edge b) {
  16.         return a.w < b.w;
  17.     }
  18. };
  19.  
  20. int N, M, Q;
  21. int T[MAXN], C[MAXN];
  22.  
  23. struct query {
  24.     int l, r, k;
  25. } qr[MAXN];
  26.  
  27.  
  28. struct Dosu {
  29.     int par[MAXN];
  30.     set<int> sz[MAXN];
  31.  
  32.     void INIT() {
  33.         for (int i = 1; i <= N; i++) {
  34.             sz[i].insert(T[i]);
  35.             par[i] = i;
  36.         }
  37.     }
  38.  
  39.     int find_set(int u) {
  40.         if (par[u] == u) return u;
  41.         return par[u] = find_set(par[u]);
  42.     }
  43.  
  44.     void union_set(int u, int v) {
  45.         u = find_set(u), v = find_set(v);
  46.         if (u == v) return;
  47.         if (sz[u].size() < sz[v].size()) swap(u, v);
  48.         par[v] = u;
  49.         for (auto E : sz[v]) sz[u].insert(E);
  50.     }
  51. } DSU;
  52.  
  53.  
  54. struct Bachcho {
  55.     int L[MAXN], R[MAXN], MID[MAXN];
  56.     vector<int> q[MAXN];
  57.  
  58.     void INIT() {
  59.         for (int i = 1; i <= Q; i++) {
  60.             L[i] = -1, R[i] = M + 1, MID[i] = (L[i] + R[i]) / 2;
  61.             q[MID[i]].pb(i);
  62.         }
  63.     }
  64.  
  65.     bool check(int id) {
  66.         if (DSU.find_set(qr[id].l) != DSU.find_set(qr[id].r)) return false;
  67.         if (DSU.sz[DSU.find_set(qr[id].l)].size() >= qr[id].k) return true;
  68.         return false;
  69.     }
  70.  
  71.     void SOLVE() {
  72.         while(1) {
  73.             DSU.INIT();
  74.  
  75.             for (int i = 0; i <= M; i++) {
  76.                 if (i > 0) DSU.union_set(B[i].u, B[i].v);
  77.                 for (auto id : q[i]) {
  78.                     if (check(id)) R[id] = MID[id];
  79.                     else L[id] = MID[id];
  80.                     if (R[id] > L[id] + 1) MID[id] = (R[id] + L[id]) / 2;
  81.                 }
  82.             }
  83.  
  84.             for (int i = 0; i <= M; i++) q[i].clear();
  85.  
  86.             bool kt = 0;
  87.             for (int i = 1; i <= Q; i++) {
  88.                 if (R[i] <= L[i] + 1) continue;
  89.                 kt = 1;
  90.                 q[MID[i]].pb(i);
  91.             }
  92.             if (!kt) break;
  93.         }
  94.     }
  95. } PBS;
  96.  
  97.  
  98.  
  99. signed main() {
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0);
  102.     cout.tie(0);
  103.  
  104. //    freopen("a.inp", "r", stdin);
  105. //    freopen("a.out", "w", stdout);
  106.  
  107.     cin >> N >> M >> Q;
  108.     for (int i = 1; i <= N; i++) {
  109.         cin >> T[i];
  110.     }
  111.  
  112.  
  113.     for (int i = 1; i <= M; i++) {
  114.         int u, v, w;
  115.         cin >> u >> v >> w;
  116.         B[i] = {u, v, w};
  117.  
  118.     }
  119.     sort (B + 1, B  + M + 1, cmp());
  120.  
  121.     for (int i = 1; i <= M; i++) C[i] = B[i].w;
  122. ;
  123.     for (int i = 1; i <= Q; i++) {
  124.         cin >> qr[i].l >>  qr[i].r >> qr[i].k;
  125.     }
  126.  
  127.     PBS.INIT();
  128.     PBS.SOLVE();
  129.  
  130.     for (int i = 1; i <= Q; i++) {
  131.         if (PBS.R[i] > M) cout << -1 << '\n';
  132.         else cout << C[PBS.R[i]] << '\n';
  133.     }
  134. }
  135.  
Success #stdin #stdout 0.01s 11664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UztU5P
language:
C++14 (gcc 8.3)
created:
8 days 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!