fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3")
  4. #pragma GCC optimize("O1")
  5. #pragma GCC optimize("O1")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize(3)
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC optimize("inline")
  10. #pragma GCC optimize("-fgcse")
  11. #pragma GCC optimize("-fgcse-lm")
  12. #pragma GCC optimize("-fipa-sra")
  13. #pragma GCC optimize("-ftree-pre")
  14. #pragma GCC optimize("-ftree-vrp")
  15. #pragma GCC optimize("-fpeephole2")
  16. #pragma GCC optimize("-ffast-math")
  17. #pragma GCC optimize("-fsched-spec")
  18. #pragma GCC optimize("-falign-jumps")
  19. #pragma GCC optimize("-falign-loops")
  20. #pragma GCC optimize("-falign-labels")
  21. #pragma GCC optimize("-fdevirtualize")
  22. #pragma GCC optimize("-fcaller-saves")
  23. #pragma GCC optimize("-fcrossjumping")
  24. #pragma GCC optimize("-fthread-jumps")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")
  47. #define int long long
  48. #define cint const int
  49. #define ii pair<int, int>
  50. #define fi first
  51. #define se second
  52. #define vi vector<int>
  53. #define vii vector<vi>
  54. #define pb push_back
  55. #define pq priority_queue
  56. #define mid(l, r) ((l + r) >> 1)
  57. #define left(id) (id << 1)
  58. #define cntbit(mask) __builtin_popcountll(mask)
  59. #define BIT(mask, i) (mask & (1ll << (i)))
  60. #define ONBIT(mask, i) (mask | (1ll << (i)))
  61.  
  62. const int MAXN = 1e5 + 15;
  63. const int oo   = 1e18;
  64. const int MOD  = 1e9 + 7;
  65.  
  66. struct Edge {
  67.      int u, v, w;
  68. } B[MAXN];
  69.  
  70. struct cmp {
  71.     bool operator() (Edge a, Edge b) {
  72.         return a.w < b.w;
  73.     }
  74. };
  75.  
  76. int N, M, Q;
  77. int T[MAXN], C[MAXN];
  78.  
  79. struct query {
  80.     int l, r, k;
  81. } qr[MAXN];
  82.  
  83.  
  84. struct Dosu {
  85.     int par[MAXN];
  86.     set<int> sz[MAXN];
  87.  
  88.     void INIT() {
  89.         for (int i = 1; i <= N; i++) {
  90.             sz[i].insert(T[i]);
  91.             par[i] = i;
  92.         }
  93.     }
  94.  
  95.     int find_set(int u) {
  96.         if (par[u] == u) return u;
  97.         return par[u] = find_set(par[u]);
  98.     }
  99.  
  100.     void union_set(int u, int v) {
  101.         u = find_set(u), v = find_set(v);
  102.         if (u == v) return;
  103.         if (sz[u].size() < sz[v].size()) swap(u, v);
  104.         par[v] = u;
  105.         for (auto E : sz[v]) sz[u].insert(E);
  106.     }
  107. } DSU;
  108.  
  109.  
  110. struct Bachcho {
  111.     int L[MAXN], R[MAXN], MID[MAXN];
  112.     vector<int> q[MAXN];
  113.  
  114.     void INIT() {
  115.         for (int i = 1; i <= Q; i++) {
  116.             L[i] = 0, R[i] = M + 1, MID[i] = (L[i] + R[i]) / 2;
  117.             q[MID[i]].pb(i);
  118.         }
  119.     }
  120.  
  121.     bool check(int id) {
  122.         if (DSU.find_set(qr[id].l) != DSU.find_set(qr[id].r)) return false;
  123.         if (DSU.sz[DSU.find_set(qr[id].l)].size() >= qr[id].k) return true;
  124.         return false;
  125.     }
  126.  
  127.     void SOLVE() {
  128.         while(1) {
  129.             DSU.INIT();
  130.             for (int i = 1; i <= M; i++) {
  131.                 DSU.union_set(B[i].u, B[i].v);
  132.                 for (auto id : q[i]) {
  133.                     if (check(id)) R[id] = MID[id];
  134.                     else L[id] = MID[id];
  135.                     if (R[id] > L[id] + 1) MID[id] = (R[id] + L[id]) / 2;
  136.                 }
  137.             }
  138.  
  139.             for (int i = 1; i <= M; i++) q[i].clear();
  140.             bool kt = 0;
  141.             for (int i = 1; i <= Q; i++) {
  142.                 if (R[i] <= L[i] + 1) continue;
  143.                 kt = 1;
  144.                 q[MID[i]].pb(i);
  145.             }
  146.             if (!kt) break;
  147.         }
  148.     }
  149. } PBS;
  150.  
  151.  
  152.  
  153. signed main() {
  154.     ios_base::sync_with_stdio(0);
  155.     cin.tie(0);
  156.     cout.tie(0);
  157.  
  158. //    freopen("a.inp", "r", stdin);
  159. //    freopen("a.out", "w", stdout);
  160.  
  161.     cin >> N >> M >> Q;
  162.     for (int i = 1; i <= N; i++) {
  163.         cin >> T[i];
  164.     }
  165.  
  166.  
  167.     for (int i = 1; i <= M; i++) {
  168.         int u, v, w;
  169.         cin >> u >> v >> w;
  170.         B[i] = {u, v, w};
  171.  
  172.     }
  173.     sort (B + 1, B  + M + 1, cmp());
  174.  
  175.     for (int i = 1; i <= M; i++) C[i] = B[i].w;
  176. ;
  177.     for (int i = 1; i <= Q; i++) {
  178.         cin >> qr[i].l >>  qr[i].r >> qr[i].k;
  179.     }
  180.  
  181.     PBS.INIT();
  182.     PBS.SOLVE();
  183.  
  184.     for (int i = 1; i <= Q; i++) {
  185.         if (PBS.R[i] > M) cout << " -1\n";
  186.         else cout << C[PBS.R[i]] << '\n';
  187.     }
  188. }
  189.  
Success #stdin #stdout 0.01s 13624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/35ClLt
language:
C++14 (gcc 8.3)
created:
2 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!