oj.uz

Submission #872669

# Submission time Handle Problem Language Result Execution time Memory
872669 2023-11-13T14:06:39 Z VinhLuu Harbingers (CEOI09_harbingers) C++17
100 / 100
 72 ms 24120 KB 
#include <bits/stdc++.h>
#define int long long
#define Max 100005
#define pb push_back
#define fi first
#define se second
using namespace std;

typedef pair<int,int> pii;
struct ele{
    int pos,to;
    pii o;
};
int s[Max],v[Max],n,d[Max],top;
int dp[Max];
vector<pii> p[Max];
pii line[Max];
vector<ele> lt;

bool check(pii a,pii b,pii c){
    return (double)((c.se - a.se))/((double)(a.fi - c.fi)) < ((double)(b.se - a.se))/((double)(a.fi - b.fi));
}


int cal(pii a,int b){
    return a.fi * b + a.se;
}

void add(pii x){

    int l = 1, r = top - 1, k = top;

    while(l <= r){
        int mid = (l + r)/2;
        if(check(line[mid - 1],line[mid],x)){
            k = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    ele lmao;
    lmao.pos = k; lmao.to = top; lmao.o = line[k];
    lt.push_back(lmao);
    top = k + 1;
    line[k] = x;
}

void undo(){
    ele h = lt.back(); lt.pop_back();
    top = h.to; line[h.pos] = h.o;
}

int query(int u){
    if(top == 0) return 0;
    int l = 0, r = top - 1, ans = cal(line[l],u);
    while(l < r){
      int mid = (l + r)/2;
        int g1 = cal(line[mid],u);
        int g2 = cal(line[mid+1],u);
        if(g1 > g2) l = mid + 1; else r = mid;
        ans = min({ans,min(g1,g2)});
    }
    return ans;
}

void dfs(int u,int vi){
    if(u != 1) dp[u] = query(v[u]) + v[u]*d[u] + s[u];
    add({-d[u],dp[u]});
    for(auto jj : p[u]){
        int j = jj.first;
        int kc = jj.second;
        if(j == vi) continue;
        d[j] = d[u] + kc;
        dfs(j,u);
    }
    undo();
}


signed main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 
    cin >> n;
    for(int i = 1; i < n; i ++){
        int x,y,c;
        cin >> x >> y >> c;
        p[x].push_back({y,c});
        p[y].push_back({x,c});
    }
    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] << " ";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Correct 28 ms 14272 KB Output is correct
4 Correct 51 ms 17344 KB Output is correct
5 Correct 54 ms 22724 KB Output is correct
6 Correct 64 ms 24120 KB Output is correct
7 Correct 35 ms 15300 KB Output is correct
8 Correct 71 ms 19592 KB Output is correct
9 Correct 72 ms 20792 KB Output is correct
10 Correct 70 ms 19612 KB Output is correct