제출 #404666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404666		nikatamliani	Harbingers (CEOI09_harbingers)	C++14	0 / 100	220 ms	65312 KiB

harbingers

#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] << ' ';
	}
}

컴파일 시 표준 에러 (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]

• Subtask 1: 0 / 100