fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ull unsigned ll
  6. #define ld long double
  7. #define eb emplace_back
  8. #define ef emplace_front
  9. #define pii pair <int, int>
  10. #define pli pair <ll, int>
  11. #define pll pair <ll, ll>
  12. #define pci pair <char, int>
  13. #define pil pair <int, ll>
  14. #define pic pair <int, char>
  15. #define pib pair <int, bool>
  16. #define pbi pair <bool, int>
  17. #define pcc pair <char, char>
  18. #define fi first
  19. #define se second
  20. #define all(ac) ac.begin(), ac.end()
  21. #define MASK(x) (1 << (x))
  22. #define ub(i, j) (((i) >> (j)) & 1)
  23. #define FBIT(x) (MASK(x) - 1)
  24. #define FLIP(x, y) (FBIT(x) ^ (y))
  25. #define bit_count(x) (int) (__builtin_popcount(x))
  26. #define bit_countll(x) (int) (__builtin_popcountll(x))
  27. #define ii make_pair
  28. #define int128 __int128_t
  29. #define SZ(x) ((int) x.size())
  30. #define UNIQUE(IV) (sort(all(IV)), IV.erase(unique(all(IV)), IV.end()))
  31. #define multi 0
  32.  
  33. const int MX = 2e5 + 5;
  34. int n, m, Q;
  35. int a[MX];
  36. int high[MX];
  37. int par[MX][19];
  38. int lchild[MX], rchild[MX];
  39. int ans[MX], w[MX];
  40.  
  41. struct edge {
  42.     int u, v, w;
  43.     edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
  44.  
  45.     bool operator <(const edge &other) const {
  46.         return w > other.w;
  47.     }
  48. } e[MX];
  49.  
  50. vector <edge> Qr[MX];
  51.  
  52. int lab[MX];
  53. int tin[MX], tout[MX], A[MX];
  54.  
  55. int find(int u) {
  56.     return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  57. }
  58.  
  59. void DFS(int u) {
  60.     static int timer = 0;
  61.     tin[u] = ++timer;
  62.     A[timer] = u;
  63.  
  64.     for(int i = 1; i < 19; i++) par[u][i] = par[par[u][i - 1]][i - 1];
  65.  
  66.     int v1 = lchild[u];
  67.     int v2 = rchild[u];
  68.  
  69.     if(v1) {
  70.         par[v1][0] = par[v2][0] = u;
  71.         high[v1] = high[v2] = high[u] + 1;
  72.  
  73.         DFS(v1);
  74.         DFS(v2);
  75.     }
  76.  
  77.     tout[u] = timer;
  78.  
  79.     return;
  80. }
  81.  
  82. int LG(int x) {
  83.     return !x ? -1 : __lg(x);
  84. }
  85.  
  86. int Jump(int x, int lim) {
  87.     for(int i = LG(high[x]); i >= 0; i--) if(high[x] > MASK(i)) {
  88.         if(w[par[x][i]] >= lim) {
  89.             x = par[x][i];
  90.         }
  91.     }
  92.  
  93.     return x;
  94. }
  95.  
  96. bool sameCC(int x, int y) {
  97.     return find(x) == find(y);
  98. }
  99.  
  100. struct BIT {
  101.     int n;
  102.     vector <int> bit;
  103.  
  104.     BIT(int n = 0): n(n), bit(n + 1, 0) {}
  105.  
  106.     void update(int x, int w) {
  107.         for(; x <= n; x += x&-x) bit[x] += w;
  108.         return;
  109.     }
  110.  
  111.     int get(int x) {
  112.         int res = 0;
  113.         for(; x > 0; x &= x - 1) res += bit[x];
  114.         return res;
  115.     }
  116. } bit;
  117.  
  118. void solve() {
  119.     cin >> n >> m >> Q;
  120.     for(int i = 1; i <= m; i++) {
  121.         int u, v, w; cin >> u >> v >> w;
  122.         e[i] = edge(u, v, w);
  123.     }
  124.  
  125.     vector <int> rv;
  126.     for(int i = 1; i <= n; i++) cin >> a[i], rv.eb(a[i]);
  127.  
  128.     auto get_rank = [&] (int x) -> int {
  129.         return upper_bound(all(rv), x) - rv.begin();
  130.     };
  131.  
  132.     sort(e + 1, e + m + 1);
  133.     memset(lab, -1, sizeof lab);
  134.  
  135.     int vers = n;
  136.     for(int i = 1; i <= m; i++) if(!sameCC(e[i].u, e[i].v)) {
  137.         vers++;
  138.         w[vers] = e[i].w;
  139.  
  140.         lchild[vers] = find(e[i].u);
  141.         rchild[vers] = find(e[i].v);
  142.  
  143.         lab[find(e[i].u)] = lab[find(e[i].v)] = vers;
  144.     }
  145.  
  146.     for(int i = 1; i <= n; i++) {
  147.         int u = find(i);
  148.         if(!high[u]) {
  149.             high[u] = 1;
  150.             DFS(u);
  151.         }
  152.     }
  153.  
  154.     for(int i = 1; i <= Q; i++) {
  155.         int v, h, x; cin >> v >> h >> x;
  156.         v = Jump(v, h);
  157.  
  158.         if(tin[v] > 1) Qr[tin[v] - 1].eb(x, -1, i);
  159.         Qr[tout[v]].eb(x, 1, i);
  160.  
  161.         rv.eb(x);
  162.     }
  163.  
  164.     UNIQUE(rv);
  165.     bit = BIT(SZ(rv));
  166.  
  167.     for(int i = 1; i <= vers; i++) {
  168.         int u = A[i];
  169.         if(u <= n) bit.update(get_rank(a[u]), 1);
  170.  
  171.         for(edge &x : Qr[i]) ans[x.w] += bit.get(get_rank(x.u)) * x.v;
  172.     }
  173.  
  174.     for(int i = 1; i <= Q; i++) cout << ans[i] << '\n';
  175.  
  176.     return;
  177. }
  178.  
  179. int32_t main() {
  180.     ios::sync_with_stdio(false);
  181.     cin.tie(0), cout.tie(0);
  182.     #define task "tet"
  183.     if(fopen(task".inp", "r")) {
  184.         freopen(task".inp", "r", stdin);
  185.         freopen(task".out", "w", stdout);
  186.     }
  187.  
  188.     int testcase = multi == 2 ? 1e9 : 1; if(multi == 1) cin >> testcase;
  189.     while(testcase--) solve();
  190.     return 0;
  191. }
  192.  
Success #stdin #stdout 0.01s 11868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vz47yE
language:
C++14 (gcc 8.3)
created:
7 hours 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!