Submission #1211064

#TimeUsernameProblemLanguageResultExecution timeMemory
1211064dostsHarbingers (CEOI09_harbingers)C++20
20 / 100
73 ms20924 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e9, inf = 2e9,MAXN = 1e6+1; const int N = 1e5+1; int s[N],v[N],d[N]; long long dp[N]; vector<pii> edges[N]; struct Line { int m; long long b; long long eval(int x) { return 1LL*m*x+b; } }; Line lines[400001]; pair<int,Line> upds[20000]; int ids = 0; int ptr = 0; vi vals; int idx(int x) { return upper_bound(all(vals),x)-vals.begin(); } void update(int node, int l,int r,Line& line) { if (line.m == inf && line.b == inf) return; int m = (l+r) >> 1; bool good = lines[node].eval(vals[l-1]) > line.eval(vals[l-1]); bool goodmid = lines[node].eval(vals[m-1]) > line.eval(vals[m-1]); if (goodmid) { upds[ptr++] = {node,lines[node]}; swap(lines[node],line); } if (l == r) return; if (goodmid != good) update(2*node,l,m,line); else update(2*node+1,m+1,r,line); }; long long query(int node,int l,int r,const int x) { if (l == r) return lines[node].eval(vals[x-1]); int m = (l+r) >> 1; if (x <= m) return min(lines[node].eval(vals[x-1]),query(2*node,l,m,x)); return min(lines[node].eval(vals[x-1]),query(2*node+1,m+1,r,x)); } void rollback(int k) { while (k--) { lines[upds[ptr-1].ff] = upds[ptr-1].ss; ptr--; } } int n; void dfs(int node,int p,int der = 0) { d[node] = der; if (node > 1) dp[node] = s[node]+1LL*v[node]*d[node]+query(1,1,n,idx(v[node])); else dp[node] = 0; int crea = ptr; Line toadd = {-d[node],dp[node]}; update(1,1,n,toadd); int crea2 = ptr; for (auto it : edges[node]) { if (it.ff == p) continue; dfs(it.ff,node,der+it.ss); } edges[node].clear(); rollback(crea2-crea); } void solve() { cin >> n; for (int i = 1;i<=4*n;i++) lines[i] = {inf,inf}; for (int i=1;i<n;i++) { int a,b,c; cin >> a >> b >> c; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } for (int i=2;i<=n;i++) cin >> s[i] >> v[i]; for (int i=2;i<=n;i++) vals.push_back(v[i]); sort(all(vals)); vals.erase(unique(all(vals)),vals.end()); int nn = n; n = vals.size(); dfs(1,1); for (int i=2;i<=nn;i++) cout << dp[i] << ' '; cout << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef Dodi freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...