| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 926296 | Karoot | Harbingers (CEOI09_harbingers) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
if (empty())return linf;
auto l = *lower_bound(x);
return l.k * x + l.m;
}
bool eras(ll k, ll m){
auto it = find({k, m, 0});
if ((*it).k == k && (*it).m == m){
erase(it);
return true;
}
return false;
}
};
const int MAXN = 1e5+4;
LineContainer LC;
vector<int> children[MAXN];
ll d[MAXN];
vector<pair<int, int>> adj[MAXN];
ll w[MAXN], s[MAXN];
ll dp[MAXN];
void buildTree(int node, int parent, ll w){
d[node] = w;
for (auto p : adj[node]){
if (p.first != parent){
children[node].push_back(p.first);
buildTree(p.first, node, w+p.second);
}
}
}
void dfs(int node){
if (node == 0){
dp[node] = 0;
} else {
dp[node] = -LC.query(w[node]) + s[node] + d[node]*w[node];
}
for (int x : children[node]){
LC.add(d[node], -dp[node]);
dfs(x);
}
//cout << node << ": " << endl;
LC.eras(d[node], -dp[node]);
}
int main(){
scoobydoobydoo();
int n; cin >> n;
for (int i = 0; i < n-1; i++){
ll a, b, w; cin >> a >> b >> w;
a--; b--;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
buildTree(0, 0, 0);
for (int i = 1; i < n; i++){
cin >> s[i] >> w[i];
}
dfs(0);
//for (int i = 0; i < n; i++)cout << i << ": " << d[i] << endl;
for (int i = 1; i < n; i++)cout << dp[i] << " ";
cout << endl;
return 0;
}