fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include<ext/pb_ds/assoc_container.hpp>
  5. #include<ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. template <typename T>
  8. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9.  
  10. //0 1->codeforces
  11. #define LL "%lld"
  12. #define fi first
  13. #define se second
  14. #define pb push_back
  15. #define mp make_pair
  16. #define PN printf("\n")
  17. #define MODV 1000000007
  18. #define MAXN 100007
  19.  
  20. typedef long long ll;
  21. typedef double dbl;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vll;
  24. typedef pair<int, int> pi;
  25. void addmod(int &a, ll b){a=(a+b); if(a>=MODV)a-=MODV;}
  26. void mulmod(int &a, ll b){a=(a*b)%MODV;}
  27. int gi(){int a;scanf("%d",&a);return a;}
  28. ll gll(){ll a;scanf(LL,&a);return a;}
  29.  
  30. typedef vector<ll> opi;
  31. //ordered_set<opi> os[MAXN];
  32. ll ans[MAXN], dw[MAXN];
  33. vector<pi> vq[MAXN];
  34.  
  35. class graphwal
  36. {
  37.   public:
  38.     //1 1->bidirectional, 2->reverse edges
  39.     typedef vector<pair<int,int>> vpi;
  40.  
  41.     int n, q;
  42.     vector<vpi> ed;
  43.  
  44.     graphwal(int n):n(n),ed(n){}
  45.     void add(int a, int b, ll w){
  46.       if(ed[a].size()==0)ed[a].reserve(8);
  47.       if(ed[b].size()==0)ed[b].reserve(8);
  48.       ed[a].pb(mp(b,w));ed[b].pb(mp(a,w));
  49.     }
  50.     void load(int m){ for(int i=0;i<m;i++){int a=gi(),b=gi();int w=gi();add(a-1,b-1,w);}}
  51.     void loadq(int q){
  52.       this->q = q;
  53.       int v;int k;
  54.       for(int i=0;i<q;i++){
  55.         v=gi()-1;k=gi();
  56.         if(k>n)ans[i]=-1;
  57.         else{
  58.           if(vq[v].size()==0)vq[v].reserve(8);
  59.           vq[v].pb({k,i});
  60.         }
  61.       }
  62.     }
  63.     void merge(opi &oa, opi &ob, int ia, int ib){
  64.       if(oa.size()<ob.size()){
  65.         swap(oa,ob);
  66.         swap(dw[ia],dw[ib]);
  67.       }
  68.       ll diff=dw[ib]-dw[ia];
  69.       if(ob.size()==0)return;
  70.       //size_t ns = oa.size() + ob.size() +8;
  71.       //if(ns>oa.capacity()) oa.reserve(ns);
  72.       for(auto &i:ob){ i+=diff; }
  73.       move(ob.begin(),ob.end(),back_inserter(oa));
  74.     }
  75.     opi dfs(int v=0, int pa=-1){
  76.       bool leaf=true;
  77.       opi o;
  78.       for(auto i:ed[v])
  79.         if(i.fi!=pa){
  80.           leaf=false;
  81.           opi t=dfs(i.fi,v);
  82.           dw[i.fi]+=i.se;
  83.           merge(o,t,v,i.fi);
  84.         }
  85.       bool sorted=false;
  86.       for(auto i:vq[v]){
  87.         if(i.fi>o.size()){
  88.           ans[i.se]=-1;
  89.         }else{
  90.           if(!sorted)sort(o.begin(),o.end()),sorted=true;
  91.           ans[i.se]=o[i.fi-1]+dw[v];
  92.         }
  93.       }
  94.       //o.insert({-dw[v],v});
  95.       o.pb(-dw[v]);
  96.       return o;
  97.     }
  98.     void print(){
  99.       for(int i=0;i<q;i++){
  100.         printf("%lld\n",ans[i]);
  101.       }
  102.     }
  103. };
  104. int main() {
  105.   int n=gi();
  106.   graphwal g(n);
  107.   g.load(n-1);
  108.   g.loadq(gi());
  109.   g.dfs();
  110.   g.print();
  111.  
  112.   return 0;
  113. }
  114.  
Runtime error #stdin #stdout #stderr 0s 7220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/EvNAot
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!