Submission #933837

#	Time	Username	Problem	Language	Result	Execution time	Memory
933837		dosts	Harbingers (CEOI09_harbingers)	C++17	0 / 100	86 ms	36432 KiB

harbingers

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+1,M = 2e2+1,inf = 2e18;

struct CHT{
    deque<long long> times;
    deque<pair<int, long long>> lines;
    long long intersect(pair<int, long long> a,pair<int, long long> b){
        if(b.first > a.first) swap(a,b);
        if(b.second - a.second < 0) return (b.second - a.second) / (a.first - b.first);
        return (b.second - a.second + (a.first - b.first - 1)) / (a.first - b.first);
    }
    void add(pair<int,long long> x){
        while(lines.size() > 0 && intersect(lines.back(),x) <= times.back()){
            lines.pop_back();
            times.pop_back();
        }
        if(lines.empty()){
            lines.push_back(x);
            times.push_back(0);
        }
        else{
            times.push_back(intersect(x,lines.back()));
            lines.push_back(x);
        }
    }
    long long query(int x){
        while(lines.size() > 1 && times[1] <= x){
            lines.pop_front();
            times.pop_front();
        }
        assert(lines.size());
        return lines.front().second + (long long)x*lines.front().first;
    }
};

vector<pii> edges[N];
vi d(N);

void dfs(int node,int p,int dep = 0) {
    d[node] = dep;
    for (auto it : edges[node]) if (it.first != p) dfs(it.first,node,dep+it.second);
}

void solve() {
    int n;
    cin >> n;
    vi t(n+1),w(n+1);
    for (int i=1;i<=n-1;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    w[0] = t[0] = 0;
    for (int i=2;i<=n;i++) cin >> w[i] >> t[i];
    dfs(1,1);
    vi order(n+1);
    for (int i=1;i<=n;i++) order[i] = i;
    sort(order.begin()+1,order.end(),[&](int x,int y) {
        return d[x] < d[y];
    });
    vi dp(n+1);
    CHT cht;
    for (int i=1;i<=n;i++) {
        int node = order[i];
        if (node > 1)dp[node] = cht.query(t[node])+w[node]+d[node]*t[node];
        else dp[node] = 0;
        cht.add({-d[node],dp[node]});
    }
    for (int i=2;i<=n;i++) cout << dp[i] << " ";
    cout << '\n';
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 0 / 100