Submission #404666

#TimeUsernameProblemLanguageResultExecution timeMemory
404666nikatamlianiHarbingers (CEOI09_harbingers)C++14
0 / 100
220 ms65312 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N = 1e5+10, oo = 4e18; vector<pair<int, int>> edges[N]; int p[N], s[N], v[N], sum[N]; ll dp[N], n; void mini(ll &x, ll y) { if(x > y) { x = y; } } struct line { ll k, b; line(ll _k, ll _b) : k(_k), b(_b) {} line() : line(0, 4e18) {} ll f(ll x) { return k*x + b; } }; struct node { node *L, *R; line l; node() : L(NULL), R(NULL), l() {} } *root; pair<line*, line> ops[500005]; int timer = 0; void add_line(ll l, ll r, line ln, node *&t) { if(t == NULL) t = new node(); ll m = l + r >> 1; bool lft = t->l.f(l) < ln.f(l); bool mid = t->l.f(m) < ln.f(m); if(lft == mid && !lft) { swap(ln, t->l); if(timer <= 5e5)ops[++timer] = pair<line*, line>{&(t->l), t->l}; } if(lft != mid && !mid) { swap(ln, t->l); if(timer <= 5e5)ops[++timer] = pair<line*, line>{&(t->l), t->l}; } if(l == r) { return; } if(lft == mid) { add_line(m+1, r, ln, t->R); } else { add_line(l, m, ln, t->L); } } ll get_min(ll l, ll r, ll x, node *&t) { if(t == NULL || l > x || r < x) return oo; if(l == r) return t->l.f(x); return min({get_min(l, l+r>>1, x, t->L), get_min((l+r>>1)+1, r, x, t->R), t->l.f(x)}); } void rollback(int T) { while(timer > T) { *(ops[timer].first) = ops[timer--].second; } } void dfs(int x, int p) { int T = timer; if(x == 1) { dp[x] = 0; } else { dp[x] = get_min(1, 1e9, v[x], root) + (ll)sum[x] * v[x] + (ll)s[x]; } add_line(1, 1e9, line(-sum[x], dp[x]), root); for(pair<int, int> to : edges[x]) { if(to.first != p) { sum[to.first] = sum[x] + to.second; dfs(to.first, x); } } rollback(T); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i < n-1; ++i) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({v, w}); edges[v].push_back({u, w}); } for(int i = 2; i <= n; ++i) { cin >> s[i] >> v[i]; } dfs(1, 0); for(int i = 2; i <= n; ++i) { cout << dp[i] << ' '; } }

Compilation message (stderr)

harbingers.cpp: In function 'void add_line(long long int, long long int, line, node*&)':
harbingers.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  ll m = l + r >> 1;
      |         ~~^~~
harbingers.cpp: In function 'long long int get_min(long long int, long long int, long long int, node*&)':
harbingers.cpp:53:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  return min({get_min(l, l+r>>1, x, t->L), get_min((l+r>>1)+1, r, x, t->R), t->l.f(x)});
      |                         ~^~
harbingers.cpp:53:53: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  return min({get_min(l, l+r>>1, x, t->L), get_min((l+r>>1)+1, r, x, t->R), t->l.f(x)});
      |                                                    ~^~
harbingers.cpp: In function 'void rollback(int)':
harbingers.cpp:57:34: warning: operation on 'timer' may be undefined [-Wsequence-point]
   57 |   *(ops[timer].first) = ops[timer--].second;
      |                             ~~~~~^~
harbingers.cpp:57:34: warning: operation on 'timer' may be undefined [-Wsequence-point]
#Verdict Execution timeMemoryGrader output
Fetching results...