| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 197305 | quocnguyen1012 | Harbingers (CEOI09_harbingers) | C++14 | 292 ms | 47052 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define taskname "HARBINGERS"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;
vector<ii> adj[maxn];
ii a[maxn];
ll f[maxn];
int p[maxn];
ll dep[maxn];
int n;
int nTime = 0 , in[maxn] , out[maxn];
struct point{
ll x , y;
point(){};
point(ll x , ll y):x(x),y(y){};
point operator - (const point & other){
return point(x - other.x , y - other.y);
}
ll operator * (const point & other){
return x * other.y - y * other.x;
}
ll Val(int k){
return x * k + y;
}
};
bool ccw(point a , point b , point c){
return (a - b) * (c - b) <= 0;
}
struct convex{
vector<point> p;
void add(point now){
if(p.size() && now.x == p.back().x && now.y > p.back().y){
return;
}
while(p.size() >= 2 && ccw(p[p.size() - 2],p[p.size() - 1],now))
p.pop_back();
p.pb(now);
}
ll query(int x){
if(p.size() == 0)return 1e18;
int l = 0 , h = p.size() - 1;
while(l <= h){
int mid = l + h >> 1;
if(mid + 1 < p.size() && p[mid].Val(x) >= p[mid + 1].Val(x)){
l = mid + 1;
}else{
h = mid - 1;
}
}
return p[l].Val(x);
}
}s[maxn * 4];
void dfs1(int u , int par){
in[u] = ++nTime;
for(auto c : adj[u]){
if(c.first != par){
dfs1(c.first , u);
}
}
out[u] = nTime;
}
void update(int x , int l , int r , int L , int R , point now){
if(L > r || l > R)return;
if(L <= l && r <= R){
s[x].add(now);
return;
}
int mid = l + r >> 1;
update(x * 2 , l , mid , L , R , now);
update(x * 2 + 1 , mid + 1 , r , L , R , now);
}
ll query(int x , int l , int r , int pos , int k){
if(l == r)return s[x].query(k);
int mid = l + r >> 1;
if(mid >= pos)return min(s[x].query(k),query(x*2,l,mid,pos,k));
return min(s[x].query(k),query(x*2+1,mid+1,r,pos,k));
}
void dfs(int u,int par){
f[u] = 1e18;
if(u == 1)f[u] = 0;
else{
f[u] = query(1,1,n,in[u],a[u].second) + a[u].first + dep[u] * a[u].second;
}
update(1,1,n,in[u],out[u],point(-dep[u],f[u]));
for(ii c : adj[u]){
if(c.first == par)continue;
dep[c.first] = dep[u] + c.second;
dfs(c.first , u);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".IN","r")){
freopen(taskname".IN","r",stdin);
freopen(taskname".OUT","w",stdout);
}
cin >> n;
for(int i = 1 ; i < n ; ++i){
int u , v , c;cin >> u >> v >> c;
adj[u].pb(mp(v,c));adj[v].pb(mp(u,c));
}
for(int i = 2 ; i <= n ; ++i)cin >> a[i].first >> a[i].second;
dfs1(1,0);
dfs(1,0);
for(int i = 2 ; i <= n ; ++i)cout << f[i] << " ";
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||