fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC optimize("unroll-loops")
  4. #include<bits/stdc++.h>
  5.  
  6. using namespace std;
  7. #define ll long long
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define MAX 200200
  12.  
  13. struct segtree
  14. {
  15.     int n;
  16.     vector<ll> st;
  17.     segtree(int _n)
  18.     {
  19.         n = _n;
  20.         st.resize(n*4,0);
  21.     }
  22.  
  23.     void update(int id, int l, int r, int pos, int val)
  24.     {
  25.         if(l == r){
  26.             st[id] += val;
  27.         }else{
  28.             int m = (l+r)>>1;
  29.             if(pos <= m) update(id<<1,l,m,pos,val);
  30.             else update(id<<1|1,m+1,r,pos,val);
  31.             st[id] = st[id<<1] + st[id<<1|1];
  32.         }
  33.     }
  34.  
  35.     ll get(int id, int l, int r, int u, int v)
  36.     {
  37.         if(r < u || v < l) return 0;
  38.         if(u <= l && r <= v) return st[id];
  39.         int m = (l+r)>>1;
  40.         return get(id<<1,l,m,u,v) + get(id<<1|1,m+1,r,u,v);
  41.     }
  42. };
  43.  
  44. int n,m,q,root;
  45. vector<pair<int,int> > adjj[MAX];
  46. ll d[MAX];
  47. int par[MAX], depth[MAX], sz[MAX], head[MAX], pos[MAX];
  48. int cnt = 0;
  49. vector<int> adj[MAX];
  50.  
  51. void nhap()
  52. {
  53.     memset(d,0x3f,sizeof(d));
  54.     cin >> n >> m >> root >> q;
  55.     for(int i = 1; i<=m; i++){
  56.         int a,b,c; cin >> a >> b >> c;
  57.         adjj[a].pb({b,c});
  58.         adjj[b].pb({a,c});
  59.     }
  60. }
  61.  
  62. void dijkstra()
  63. {
  64.     d[root] = 0;
  65.     priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq;
  66.     pq.push({0,root});
  67.     while(!pq.empty()){
  68.         pair<ll,int> top = pq.top(); pq.pop();
  69.         if(top.fi != d[top.se]) continue;
  70.         for(pair<int,int> u : adjj[top.se]){
  71.             if(d[u.fi] > top.fi + u.se){
  72.                 d[u.fi] = top.fi + u.se;
  73.                 pq.push({d[u.fi], u.fi});
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. void pre_compute()
  80. {
  81.     for(int i = 1; i<=n; i++) if(i != root){
  82.         int cur = n+1;
  83.         for(pair<int,int> u : adjj[i]) if(d[u.fi] + u.se == d[i]){
  84.             cur = min(cur, u.fi);
  85.         }
  86.         if(cur != n+1){
  87.             adj[cur].pb(i);
  88.             adj[i].pb(cur);
  89.         }
  90.     }
  91.     par[root] = 0;
  92.     depth[root] = 0;
  93. }
  94.  
  95. void dfs(int v)
  96. {
  97.     int ind = -1;
  98.     sz[v] = 1;
  99.     for(int i = 0; i<adj[v].size(); i++) if(adj[v][i] != par[v]){
  100.         int u = adj[v][i];
  101.         par[u] = v;
  102.         depth[u] = depth[v]  +1;
  103.         dfs(u);
  104.         sz[v] += sz[u];
  105.         if(ind == -1 || sz[u] > sz[adj[v][ind]]) ind = i;
  106.     }
  107.     if(ind != -1 && ind != 0) swap(adj[v][0], adj[v][ind]);
  108. }
  109.  
  110. void decompose(int v, int h)
  111. {
  112.     head[v] = h;
  113.     pos[v] = ++cnt;
  114.     for(int u : adj[v]) if(u != par[v]){
  115.         if(u == adj[v][0]) decompose(u,h);
  116.         else decompose(u,u);
  117.     }
  118. }
  119.  
  120. void process()
  121. {
  122.     segtree st(n);
  123.     while(q--){
  124.         int t; cin >> t;
  125.         if(t == 1){
  126.             int u, val; cin >> u >> val;
  127.             st.update(1,1,n,pos[u],val);
  128.         }else{
  129.             int u, v; cin >> u >> v;
  130.             ll ans = 0;
  131.             while(head[u] != head[v]){
  132.                 if(depth[head[u]] < depth[head[v]]) swap(u,v);
  133.                 ans += st.get(1,1,n,pos[head[u]], pos[u]);
  134.                 u = par[head[u]];
  135.             }
  136.             if(depth[u] > depth[v]) swap(u,v);
  137.             ans += st.get(1,1,n,pos[u], pos[v]);
  138.             cout << ans << '\n';
  139.         }
  140.     }
  141. }
  142.  
  143.  main()
  144. {
  145.     ios_base::sync_with_stdio(0); cin.tie(0);
  146.     nhap();
  147.     dijkstra();
  148.     pre_compute();
  149.     dfs(root);
  150.     decompose(root,root);
  151.     process();
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0.01s 18380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4TJQ4r
language:
C++ (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!