제출 #404642

#제출 시각아이디문제언어결과실행 시간메모리
404642nikatamlianiHarbingers (CEOI09_harbingers)C++14
20 / 100
192 ms47984 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N = 2e5+10, oo = 4e18; vector<pair<int, int>> edges[N]; int p[N], s[N], v[N], sum[N], n; ll dp[N]; void mini(ll &x, ll y) { if(x > y) { x = y; } } struct line { int k; ll b; line(int _k, ll _b) : k(_k), b(_b) {} line() : line(0, 4e18) {} ll f(int x) { return (ll)k*x + b; } }; struct node { node *L, *R; line l; node() : L(NULL), R(NULL), l() {} } *root; pair<line*, line> ops[1000005]; 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) { line save = t->l; pair<line*, line> p = {&(t->l), save}; swap(ln, t->l); if(timer <= 1e6)ops[++timer] = p; } if(lft != mid && !mid) { line save = t->l; pair<line*, line> p = {&(t->l), save}; swap(ln, t->l); if(timer <= 1e6)ops[++timer] = p; } 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); ll m = l + r >> 1; ll children = min(get_min(l, m, x, t->L), get_min(m+1, r, x, t->R)); ll all = min(children, t->l.f(x)); return all; } void rollback(int T) { while(timer > T) { pair<line*, line> p = ops[timer--]; (*p.first) = p.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] + 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] << ' '; } }

컴파일 시 표준 에러 (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:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  ll m = l + r >> 1;
      |         ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...