| # | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1169112 | PieArmy | Harbingers (CEOI09_harbingers) | C++20 | 106 ms | 29768 KiB |
#include<bits/stdc++.h>
typedef long long ll;using namespace std;int n;vector<pair<int,ll>>komsu[100023];ll v[100023];ll opt[100023];int par[100023][17],dep[100023];ll path[100023],ans[100023];void dfs(int pos,int root){for(int i=1;i<17;i++){par[pos][i]=par[par[pos][i-1]][i-1];}int loc=pos;for(int i=17-1;i>=0;i--){if(dep[loc]-1<(1<<i))continue;if(opt[par[loc][i]]>v[pos]){loc=par[loc][i];}}loc=par[loc][0];ans[pos]+=ans[loc]+(path[pos]-path[loc])*v[pos];loc=pos;for(int i=17-1;i>=0;i--){if(dep[pos]-1<(1<<i))continue;int a=par[loc][i],b=par[a][0];if(__int128_t(ans[pos]-ans[b])*__int128_t(path[a]-path[b])<=__int128_t(ans[a]-ans[b])*__int128_t(path[pos]-path[b])){dep[pos]-=(1<<i);loc=a;}}par[pos][0]=par[loc][0];opt[pos]=ceil(double(ans[pos]-ans[par[pos][0]])/double(path[pos]-path[par[pos][0]]));for(int i=1;i<17;i++){par[pos][i]=par[par[pos][i-1]][i-1];}for(auto x:komsu[pos]){if(x.first==root)continue;path[x.first]=path[pos]+x.second;dep[x.first]=dep[pos]+1;par[x.first][0]=pos;dfs(x.first,pos);}}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);cin>>n;for(int i=1;i<n;i++){int x,y,z;cin>>x>>y>>z;komsu[x].push_back({y,z});komsu[y].push_back({x,z});}for(int i=2;i<=n;i++){cin>>ans[i]>>v[i];}dfs(1,1);for(int i=2;i<=n;i++){cout<<ans[i]<<" ";}}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||