Submission #1196723

#TimeUsernameProblemLanguageResultExecution timeMemory
1196723MuhammadSaramHarbingers (CEOI09_harbingers)C++17
70 / 100
277 ms131072 KiB
// Time: 06-05-2025 07:34:15 // Problem: A - Commando // Contest: Virtual Judge - Contest 3 // URL: https://vjudge.net/contest/714915#problem/A // Memory Limint: 64 MB // Time Limint: 500 ms #include <bits/stdc++.h> using namespace std; #define ll long long const int M = 1e5 + 1; int ve[M],dep[M]; ll dp[M]; vector<pair<pair<int,ll>,int>> v,rem[M]; vector<pair<int,int>> nei[M]; pair<ll,int> poi(int m,ll c,int m1,ll c1) { return {(c-c1),(m1-m)}; } bool comp(pair<ll,int> p,pair<ll,int> p1) { if (p.first/p.second>p1.first/p1.second) return 1; else if(p.first/p.second==p1.first/p1.second) return 1ll*p.first%p.second*p1.second>1ll*p1.first%p1.second*p.second; return 0; } void add(int m,ll c,int id) { while (v.size()>1) { pair<int,ll> p={v[v.size()-2].first.first,v[v.size()-2].first.second},p1={v.back().first.first,v.back().first.second}; if (comp(poi(p.first,p.second,m,c),poi(p.first,p.second,p1.first,p1.second))) rem[id].push_back(v.back()),v.pop_back(); else break; } v.push_back({{m,c},id}); } ll get(int x) { ll ans=1ll*v[0].first.first*x+v[0].first.second; int s=0,e=v.size(); while (s+1<e) { int mid=(s+e)/2; ll val=1ll*v[mid-1].first.first*x+v[mid-1].first.second; ll val1=1ll*v[mid].first.first*x+v[mid].first.second; if (val<val1) ans=max(ans,val1),s=mid; else ans=max(ans,val),e=mid; } return ans; } void dfs(int u,int p=0) { if (!p) add(0,0,1); else { dp[u]+=-get(-ve[u])+1ll*dep[u]*ve[u]; add(-dep[u],-dp[u],u); } while (!nei[u].empty()) { int i=nei[u].back().first,d=nei[u].back().second; nei[u].pop_back(); if (i!=p) dep[i]=dep[u]+d,dfs(i,u); } v.pop_back(); reverse(rem[u].begin(),rem[u].end()); for (auto i:rem[u]) add(i.first.first,i.first.second,i.second); rem[u].clear(); } signed main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); int n; cin>>n; for (int i=1;i<n;i++) { int u,v,d; cin>>u>>v>>d; nei[u].push_back({v,d}); nei[v].push_back({u,d}); } for (int i=2;i<=n;i++) cin>>dp[i]>>ve[i]; dfs(1); for (int i=2;i<=n;i++) cout<<dp[i]<<' '; cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...