# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
491545 | thomas_li | Harbingers (CEOI09_harbingers) | C++17 | 147 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef int num_t;
const num_t oo = (num_t) 1e9;
struct func_t {
num_t a, b;
func_t(num_t a = 0, num_t b = oo) : a(a), b(b) {}
num_t query(num_t x) {return a * x + b;}
};
struct node_t {
node_t *l, *r;
func_t f;
node_t(node_t* l = 0, node_t* r = 0, func_t f = func_t()) : l(l), r(r), f(f) {}
num_t query(num_t x) {return f.query(x);}
};
node_t* upd(node_t* p, int l, int r, int L, int R, func_t f) {
if (l > R || r < L) return p;
int M = L + (R - L >> 1);
node_t* res = p ? new node_t(p->l, p->r, p->f) : new node_t();
if (l <= L && r >= R) {
int fl = f.query(L) >= (p ? p->query(L) : oo);
int fr = f.query(R) >= (p ? p->query(R) : oo);
if (fl && fr) return res;
if (!fl && !fr) {
res->f = f;
return res;
}
int fm1 = f.query(M) >= (p ? p->query(M) : oo);
if (fl && fm1) {
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
if (!fl && !fm1) {
res->r = upd(res->r, l, r, M + 1, R, res->f);
res->f = f;
return res;
}
int fm2 = f.query(M + 1) >= (p ? p->query(M + 1) : oo);
if (fm2 && fr) {
res->l = upd(res->l, l, r, L, M, f);
return res;
}
if (!fm2 && !fr) {
res->l = upd(res->l, l, r, L, M, res->f);
res->f = f;
return res;
}
assert(0);
}
res->l = upd(res->l, l, r, L, M, f);
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
node_t* upd(node_t* p, int l, int r, int L, int R, num_t a, num_t b) {
return upd(p, l, r, L, R, func_t(a, b));
}
num_t query(node_t* p, int i, int L, int R) {
if (!p) return oo;
if (i < L || i > R) return oo;
num_t res = p->query(i);
if (L < R) {
res = min(res, query(p->l, i, L, L + R >> 1));
res = min(res, query(p->r, i, (L + R >> 1) + 1, R));
}
return res;
}
const int MM = 1e5+5;
int n,p[MM],s[MM],dp[MM],dep[MM];
vector<pi> adj[MM];
void dfs(int u, int pa, node_t* t){
dp[u] = query(t,s[u],-1e9,1e9) + p[u] + s[u]*dep[u];
if(u == 1) dp[u] = 0;
auto nxt = upd(t,-1e9,1e9,-1e9,1e9,-dep[u],dp[u]);
for(auto [v,w] : adj[u]) if(v != pa){
dep[v] = dep[u]+w;
dfs(v,u,nxt);
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i < n-1; i++){
int a,b,c; cin >> a >> b >> c;
adj[a].emplace_back(b,c); adj[b].emplace_back(a,c);
}
for(int i = 2; i <= n; i++){
cin >> p[i] >> s[i];
}
dfs(1,0,nullptr);
for(int i = 2; i <= n; i++) cout << dp[i] << " \n"[i==n];
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |