Submission #1263179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263179		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	100 / 100	68 ms	28328 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

//long long MOD = 1e9 + 7;
const long long MOD = 998244353;
// const long long MOD = 100000007 ;


#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define popCnt(x) (__builtin_popcountll(x))
#define int long long
#define ld long double

#define F  first
#define S  second
#define pi  M_PI
#define all(x) x.begin() , x.end()
#define LL long long
#define SZ(v) (int)(v.size())

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = LLONG_MAX / 4, N = 3e5 + 5, M = 1e5 + 5, K = 505;

struct Line {
    LL a,b;
    Line (LL a = 0,LL b = LLONG_MAX) : a(a) , b(b) {};
    LL F(LL x){
        return a*x + b;
    }
};

struct State{
    int size;
    int add_pos;
    Line val;
};

struct CHT{
public:
    long double get_intersec(Line x,Line y){
        return (long double)(y.b - x.b) / (x.a - y.a);
    }
    vector<Line> line;
    vector<State> order;
    int cur_size = 0;

    void reload_size(int n){
        line = vector<Line>(n+3,Line());
        cur_size = 0;
        return;
    }

    void add_line(Line x){
        int low = 1 , high = cur_size - 1;
        int pos = cur_size;

        while (low<=high){
            int mid = (low+high)/2;
            if (get_intersec(line[mid - 1] , line[mid]) >= get_intersec(line[mid] , x)){
                pos = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        order.push_back({cur_size , pos , line[pos]});
        cur_size = pos + 1;
        line[pos] = x;
        return;
    }

    LL Get(LL x){
        int low = 1 , high = cur_size - 1 , pos = 0;
        while (low<=high){
            int mid = (low+high)/2;
            if (get_intersec(line[mid-1],line[mid]) <= x){
                pos = mid;
                low = mid + 1;
            }
            else high = mid-1;
        }
        return line[pos].F(x);
    }

    void rollback(void){
        if (order.size()==0) return;
        int size = order.back().size;
        int pos = order.back().add_pos;
        Line val = order.back().val;

        cur_size = size; line[pos] = val;

        order.pop_back();
        return ;
    }
};

CHT cht;
int n;
vector<int> v, c;
vector<vector<pair<int, int>>> adj;

vector<int> dp;
void dfs(int node , int p = -1 , int d = 0)
{
    if(p == -1) dp[node] = 0;
    else dp[node] = cht.Get(v[node]) + v[node] * d + c[node];

    cht.add_line(Line(-d , dp[node]));

    for(auto [child , len] : adj[node])
    {
        if(child == p)continue;
        dfs(child , node , d + len);
    }
    cht.rollback();
}

signed main() {
    fast;


//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    cin >> n;
    dp = v = c = vector<int>(n);
    adj.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        int u, vv, d;
        cin >> u >> vv >> d;
        u--;
        vv--;
        adj[u].emplace_back(vv, d);
        adj[vv].emplace_back(u, d);
    }

    for (int i = 1; i < n; ++i) {
        cin >> c[i] >> v[i];
    }

    cht.reload_size(n);

    dfs(0);

    for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
    cout<<'\n';



}

• Subtask 1: 100 / 100