# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
641320 | sumit_kk10 | Harbingers (CEOI09_harbingers) | C++17 | 107 ms | 20480 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;
vector<pair<int, int> > g[N];
int n, par[N], dis[N], dp[N], s[N], d[N];
bool vis[N];
struct Line{
int m, c;
int val(int x){
return m*x + c;
}
};
vector<pair<Line, int> > hulls;
bool check(Line a, Line b, Line cc){
int x = (b.c - a.c);
x = x * (a.m - cc.m);
int y = (cc.c - a.c);
y = y * (a.m - b.m);
if(x > y)
return true;
return false;
}
void insert(int mm, int cc, int node){
Line cur;
cur.m = mm;
cur.c = cc;
if(!hulls.empty() and hulls.back().F.m == mm){
if(hulls.back().F.c > cc){
vis[hulls.back().S] = false;
hulls.pop_back();
}
else{
vis[node] = false;
return;
}
}
while(hulls.size() > 1){
if(check(hulls[hulls.size() - 2].F, hulls.back().F, cur)){
vis[hulls.back().S] = false;
hulls.pop_back();
}
else
break;
}
hulls.pb({cur, node});
}
int get(int x){
if(hulls.empty())
return 1e15;
int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1;
while(low <= high){
int mid = (low + high) / 2;
if(hulls[mid].F.val(x) <= hulls[mid + 1].F.val(x)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return hulls[ans].F.val(x);
}
void dfs(int node, int p, int sum){
dis[node] = sum;
par[node] = p;
for(auto k : g[node]){
if(k.F == p) continue;
dfs(k.F, node, sum + k.S);
}
}
void dfs1(int node){
int mn = s[node] + dis[node] * d[node];
mn = min(mn, get(d[node]) + s[node] + dis[node] * d[node]);
dp[node] = mn;
for(auto k : g[node]){
if(k.F == par[node]) continue;
if(node != 1 and !vis[node]){
vis[node] = true;
insert(-dis[node], dp[node], node);
}
dfs1(k.F);
}
if(vis[node])
hulls.pop_back();
}
void solve(){
cin >> n;
for(int i = 1; i < n; ++i){
int u, v, c;
cin >> u >> v >> c;
g[u].pb({v, c});
g[v].pb({u, c});
}
for(int i = 1; i < n; ++i)
cin >> s[i + 1] >> d[i + 1];
dfs(1, 0, 0);
dfs1(1);
for(int i = 2; i <= n; ++i)
cout << dp[i] << " ";
}
int32_t main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |