fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_VOR = 2e5;
  18. const int MAX_M = 2e5;
  19. const int MAX_N = 1e5;
  20. const int LOG = 18;
  21.  
  22. struct Disjoint_Set_Union{
  23.     int leader[MAX_VOR + 5];
  24.  
  25.     void build(int n){
  26.         FOR(i, 1, n) leader[i] = i;
  27.     }
  28.  
  29.     int get(int u){
  30.         if(u == leader[u]) return u;
  31.         return leader[u] = get(leader[u]);
  32.     }
  33.  
  34.     void unite(int u, int v){
  35.         int x = get(u), y = get(v);
  36.         if(x == y) return;
  37.  
  38.         leader[x] = leader[y];
  39.     }
  40. }dsu;
  41.  
  42. struct Edge{
  43.     int u, v, w;
  44.  
  45.     bool operator < (const Edge &other) const{
  46.         return w > other.w;
  47.     }
  48. };
  49.  
  50. struct Query{
  51.     int l, r, t, id;
  52.  
  53.     bool operator < (const Query &other) const{
  54.         return t < other.t;
  55.     }
  56. };
  57.  
  58. vector<int> adj[MAX_VOR + 5];
  59. int val[MAX_VOR + 5];
  60. int vor;
  61.  
  62. Query queries[MAX_M + 5];
  63. int ans[MAX_M + 5];
  64.  
  65. Edge edges[MAX_M + 5];
  66. pii a[MAX_N + 5];
  67. int n, m, q;
  68.  
  69. struct Fenwick_Tree{
  70.     int tree[MAX_N + 5];
  71.  
  72.     void update(int pos, int val){
  73.         for(int i = pos; i <= n; i += i & -i) tree[i] += val;
  74.     }
  75.  
  76.     int get(int pos){
  77.         int res = 0;
  78.         for(int i = pos; i >= 1; i -= i & -i) res += tree[i];
  79.         return res;
  80.     }
  81.  
  82.     int query(int l, int r){
  83.         return get(r) - get(l - 1);
  84.     }
  85. }fen;
  86.  
  87. void Input(){
  88.     cin >> n >> m >> q;
  89.  
  90.     FOR(i, 1, m){
  91.         int u, v, w;
  92.         cin >> u >> v >> w;
  93.         edges[i] = {u, v, w};
  94.     }
  95.  
  96.     FOR(i, 1, n){
  97.         cin >> a[i].fi;
  98.         a[i].sec = i;
  99.     }
  100.     sort(a + 1, a + n + 1);
  101. }
  102.  
  103. void kruskal(){
  104.     sort(edges + 1, edges + m + 1);
  105.     dsu.build(MAX_VOR);
  106.     vor = n;
  107.  
  108.     FOR(i, 1, m){
  109.         int u = edges[i].u, v = edges[i].v;
  110.         int w = edges[i].w;
  111.  
  112.         int x = dsu.get(u), y = dsu.get(v);
  113.         if(x != y){
  114.             ++vor;
  115.             val[vor] = w;
  116.  
  117.             adj[vor].pb(x);
  118.             adj[vor].pb(y);
  119.  
  120.             dsu.unite(x, vor);
  121.             dsu.unite(y, vor);
  122.         }
  123.     }
  124. }
  125.  
  126. namespace LCA{
  127.     int par[LOG + 5][MAX_VOR + 5], depth[MAX_VOR + 5];
  128.     int L[MAX_VOR + 5], R[MAX_VOR + 5], timer;
  129.  
  130.     void dfs_lca(int u, int dad){
  131.         if(u <= n) L[u] = R[u] = ++timer;
  132.         else L[u] = INF, R[u] = -INF;
  133.  
  134.         for(int v : adj[u]) if(v != dad){
  135.             depth[v] = depth[u] + 1;
  136.             par[0][v] = u;
  137.  
  138.             dfs_lca(v, u);
  139.  
  140.             L[u] = min(L[u], L[v]);
  141.             R[u] = max(R[u], R[v]);
  142.         }
  143.     }
  144.  
  145.     void build_lca(int n){
  146.         REP(u, n, 1) if(!depth[u]){
  147.             dfs_lca(u, 0);
  148.         }
  149.  
  150.         FOR(j, 1, LOG) FOR(i, 1, n){
  151.             par[j][i] = par[j - 1][par[j - 1][i]];
  152.         }
  153.     }
  154.  
  155.     pii get_LR(int u, int w){
  156.         REP(j, LOG, 0) if(val[par[j][u]] >= w){
  157.             u = par[j][u];
  158.         }
  159.  
  160.         return {L[u], R[u]};
  161.     }
  162. } using namespace LCA;
  163.  
  164. void Prepare(){
  165.     kruskal();
  166.     build_lca(vor);
  167. }
  168.  
  169. void Solve(){
  170.     FOR(i, 1, q){
  171.         int u, w, t;
  172.         cin >> u >> w >> t;
  173.  
  174.         pii cur = get_LR(u, w);
  175.         queries[i] = {cur.fi, cur.sec, t, i};
  176.     }
  177.     sort(queries + 1, queries + q + 1);
  178.  
  179.     for(int i = 1, j = 1; i <= q; i++){
  180.         int l = queries[i].l, r = queries[i].r;
  181.         int t = queries[i].t, id = queries[i].id;
  182.  
  183.         while(j <= n && a[j].fi <= t) fen.update(L[a[j++].sec], +1);
  184.         ans[id] = fen.query(l, r);
  185.     }
  186.  
  187.     FOR(i, 1, q) cout << ans[i] << el;
  188. }
  189.  
  190. signed main(){
  191.     ios_base::sync_with_stdio(0);
  192.     cin.tie(0);
  193.  
  194.     Input();
  195.     Prepare();
  196.     Solve();
  197.  
  198.     return 0;
  199. }
  200.  
Success #stdin #stdout 0.01s 11880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kIntzC
language:
C++ (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!