Facebook
From emanlaicepsa, 3 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 90
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair<ll,ll>
  5. #define vi vector<ll>
  6. #define pb emplace_back
  7. #define fi first
  8. #define se second
  9. #define all(n) (n).begin(),(n).end()
  10. #define siz(n) (int)n.size()
  11. #define IOS ios::sync_with_stdio(0), cin.tie(0);
  12. #define dbg(x) cerr<<#x<<" = "<<x<<'\n';
  13. const ll mxn = 1000005;
  14. string name[mxn];
  15. vector<pii> E[mxn];
  16. ll len[mxn], son[mxn], mnlen[mxn], pa[mxn], ans[mxn];
  17. int N, M;
  18.  
  19. void dfs_len(int nd,int p){
  20.         ll mn_down = 1e17;
  21.         for(auto &[i,l]:E[nd]){
  22.                 if(i == p) continue;
  23.                 pa[i] = nd;
  24.                 son[nd]++;
  25.                 len[i] = len[nd] + l;
  26.                 mnlen[i] = l;
  27.                 dfs_len(i, nd);
  28.                 mn_down = min(mn_down, mnlen[i]);
  29.         }
  30.         if(mn_down < 1e17) mnlen[nd] += mn_down;
  31.         if(nd == 0) mnlen[nd] = 0;
  32. }
  33.  
  34. priority_queue<pii, vector<pii>, greater<pii>> pq;
  35. int main(){
  36.         IOS;
  37.         cin>>N>>M;
  38.         M++;
  39.         for(int i=M,p,l;i<M+N;i++){
  40.                 cin>>name[i];
  41.                 cin>>p>>l;
  42.                 E[p].pb(i,l);
  43.                 E[i].pb(p,l);
  44.         }
  45.         for(int i=1,p,l;i<M;i++){
  46.                 cin>>p>>l;
  47.                 E[p].pb(i,l);
  48.                 E[i].pb(p,l);
  49.         }
  50.         dfs_len(0, -1);
  51.         vector<pii> all_len;
  52.         for(int i=M;i<N+M;i++){
  53.                 pq.emplace(mnlen[i], i);
  54.                 all_len.pb(len[i], i);
  55.         }
  56.         sort(all(all_len));
  57.         for(auto &[d, i]: all_len){
  58.                 while(!pq.empty() && pq.top().fi <= d){
  59.                         auto [_, nd] = pq.top(); pq.pop();
  60.                         while(pa[nd] != 0){
  61.                                 nd = pa[nd];
  62.                                 son[nd]--;
  63.                                 if(son[nd] == 0 && mnlen[nd] > d){
  64.                                         pq.emplace(mnlen[nd], nd);
  65.                                         break;
  66.                                 }
  67.                                 else if(son[nd] > 0) break;
  68.                         }
  69.                 }
  70.                 ans[i] = pq.size()+1;
  71.         }
  72.         for(int i=M;i<M+N;i++){
  73.                 cout<<name[i]<<" "<<ans[i]<<'\n';
  74.         }
  75. }
  76.