fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F first
  5. #define S second
  6. #define pll pair<ll, ll>
  7. #define vll vector<ll>
  8. #define pb push_back
  9.  
  10. typedef long long ll;
  11.  
  12. const ll mxN=1e5+5;
  13. const ll LOG=18;
  14.  
  15. ll n, m;
  16. vll adj[mxN];
  17. ll d[mxN], p[mxN], c[mxN];
  18. ll dis[mxN][LOG];
  19. ll boss[mxN][LOG];
  20. ll dis2[mxN][LOG];
  21. ll boss2[mxN][LOG];
  22. set<pll> s[mxN];
  23. set<pll> s2[mxN];
  24. ll sz[mxN];
  25. bool done[mxN];
  26. priority_queue<pll, vector<pll>, greater<pll>> pq;
  27. ll ans[mxN];
  28. vll v[mxN];
  29. bool dumb[mxN];
  30.  
  31. void get_sz(ll cur, ll par){
  32.     sz[cur]=1;
  33.     for(auto &chd:adj[cur]){
  34.         if(chd==par || done[chd]) continue;
  35.         get_sz(chd, cur);
  36.         sz[cur]+=sz[chd]; 
  37.     }
  38. }
  39.  
  40. ll get_cen(ll cur, ll par, ll total){
  41.     for(auto &chd:adj[cur]){
  42.         if(chd==par || done[chd]){
  43.             continue;
  44.         }
  45.         if(sz[chd]>total/2){
  46.             return get_cen(chd, cur, total);
  47.         }
  48.     }
  49.     return cur;
  50. }
  51.  
  52. void dfs(ll cur, ll par, ll dep, ll cen, ll lev){
  53.     s2[cen].insert({dep, cur});
  54.     dis2[cur][lev]=dep;
  55.     boss2[cur][lev]=cen;
  56.     for(auto &it:v[cur]){
  57.         s[cen].insert({dep-d[it], it});
  58.         // cout<<"inserting "<<cen<<' '<<dep-d[it]<<' '<<it<<'\n';
  59.         dis[it][lev]=dep;
  60.         boss[it][lev]=cen;
  61.     }
  62.     for(auto &chd:adj[cur]){
  63.         if(chd==par || done[chd]) continue;
  64.         dfs(chd, cur, dep+1, cen, lev);
  65.     }
  66. }
  67.  
  68. void cen_decomp(ll cur, ll lev){
  69.     get_sz(cur, -1);
  70.     ll cen=get_cen(cur, -1, sz[cur]);
  71.     done[cen]=1;
  72.     dfs(cen, -1, 0, cen, lev);
  73.     for(auto &chd:adj[cen]){
  74.         if(done[chd]){
  75.             continue;
  76.         }
  77.         cen_decomp(chd, lev+1);
  78.     }
  79. }
  80.  
  81. void rem1(ll tar){
  82.     for(ll i=0;i<LOG;i++){
  83.         if(boss[tar][i]==-1) break;
  84.         s[boss[tar][i]].erase({dis[tar][i]-d[tar], tar});
  85.     }
  86. }
  87.  
  88. ll f1(ll tar){
  89.     for(ll i=LOG-1;i>=0;i--){
  90.         if(boss[tar][i]==-1) continue;
  91.         if(s2[boss[tar][i]].empty()) continue;
  92.         pll tep=*s2[boss[tar][i]].begin();
  93.         // cout<<"finding "<<tar<<' '<<i<<' '<<tep.F<<' '<<tep.S<<'\n';
  94.         if(dis[tar][i]-d[tar]+tep.F<=0){
  95.             return tep.S;
  96.         }
  97.     }
  98.     return -1LL;
  99. }
  100.  
  101. void rem2(ll tar){
  102.     for(ll i=0;i<LOG;i++){
  103.         if(boss2[tar][i]==-1) break;
  104.         s2[boss2[tar][i]].erase({dis2[tar][i], tar});
  105.     }
  106. }
  107.  
  108. ll f2(ll tar){
  109.     for(ll i=LOG-1;i>=0;i--){
  110.         if(boss2[tar][i]==-1) continue;
  111.         if(s[boss2[tar][i]].empty()) continue;
  112.         pll tep=*s[boss2[tar][i]].begin();
  113.         // cout<<"finding "<<tar<<' '<<i<<' '<<tep.F<<' '<<tep.S<<'\n';
  114.         if(dis2[tar][i]+tep.F<=0){
  115.             return tep.S;
  116.         }
  117.     }
  118.     return -1LL;
  119. }
  120.  
  121. vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C) { 
  122.     memset(boss, -1, sizeof(boss));
  123.     memset(boss2, -1, sizeof(boss2));
  124.     memset(ans, -1, sizeof(ans));
  125.     memset(dumb, 0, sizeof(dumb));
  126.     memset(done, 0, sizeof(done));
  127.     n=(ll) N;
  128.     m=(ll) M;
  129.     for(ll i=0;i<n-1;i++){
  130.         adj[A[i]].pb(B[i]);
  131.         adj[B[i]].pb(A[i]);
  132.     }
  133.     for(ll i=0;i<m;i++){
  134.         p[i]=P[i];
  135.         d[i]=D[i];
  136.     }
  137.     for(ll i=0;i<n;i++){
  138.         c[i]=C[i];
  139.     }
  140.     for(ll i=0;i<m;i++){
  141.         v[p[i]].pb(i);
  142.     }
  143.     cen_decomp(0, 0);
  144.     // for(ll i=0;i<n;i++){
  145.     //     for(ll j=0;j<LOG;j++){
  146.     //         if(boss[i][j]!=-1){
  147.     //             cout<<"boss: "<<i<<' '<<j<<' '<<boss[i][j]<<'\n';
  148.     //         }
  149.     //     }
  150.     // }
  151.     ans[0]=0;
  152.     while(true){
  153.         ll re=f1(0);
  154.         cout << re << '\n';
  155.         if(re==-1) break;
  156.         ll time=c[re];
  157.         pq.push({time, re});
  158.         rem2(re);
  159.     }
  160.     rem1(0);
  161.     while(!pq.empty()){
  162.         pll cur=pq.top(); pq.pop();
  163.         ll time=cur.F; 
  164.         ll u=cur.S;
  165.         if(dumb[u]) continue;
  166.         dumb[u]=1;
  167.         cout << u << ": ";
  168.         while(true){
  169.             ll nxt=f2(u);
  170.             cout << nxt << ":: ";
  171.             if(nxt==-1) break;
  172.             if(ans[nxt]!=-1) assert(false);
  173.             ans[nxt]=time;
  174.  
  175.             while(true){
  176.                 ll re=f1(nxt);
  177.                 cout << re << ' ';
  178.                 if(re==-1) break;
  179.                 // cout<<"from "<<nxt<<' '<<re<<'\n';
  180.                 ll time2=c[re]+ans[nxt];
  181.                 pq.push({time2, re});
  182.                 rem2(re); 
  183.             }
  184.             // pq.push({ans[nxt]+c[nxt], nxt});
  185.             rem1(nxt);
  186.         }
  187.         cout << '\n';
  188.     }
  189.     vll o(m);
  190.     for(ll i=0;i<m;i++){
  191.         o[i]=ans[i];
  192.     }
  193.     return o;
  194. }
  195. signed main(){
  196.     int N, M;
  197.     cin >> N >> M;
  198.     vector<int> A(N - 1), B(N - 1), P(M), D(M), C(N);
  199.     for (int i = 0; i < N - 1; i++)
  200.         cin >> A[i] >> B[i];
  201.     for (int i = 0; i < M; i++)
  202.         cin >> P[i] >> D[i];
  203.     for(int i = 0; i < N; i++) cin >> C[i];
  204.     vector<long long> ans = find_spread(N, M, A, B, P, D, C);
  205.     for (auto &x : ans)
  206.         cout << x << "\n";
  207. }
Success #stdin #stdout 0.01s 53388KB
comments (?)
stdin
copy 
10 10
9 3
0 6
1 8
5 1
3 2
8 7
0 4
6 5
0 9
9 0
7 2
1 0
8 1
6 3
1 2
4 6
7 2
5 1
5 4
10 12 5 9 8 21 20 6 13 5
stdout
copy 
9
-1
9: 6:: 4 0 6 3 5 1 2 8 7 -1 4:: -1 9:: -1 -1:: 
2: -1:: 
7: 1:: -1 7:: -1 3:: -1 5:: -1 -1:: 
4: -1:: 
3: -1:: 
0: -1:: 
1: 2:: -1 8:: -1 -1:: 
8: -1:: 
6: -1:: 
5: -1:: 
0
11
17
11
5
11
5
11
17
5
https://ideone.com/52fpHq
language:
C++14 (gcc 8.3)
created:
281 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!