Submission #1123524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123524		AverageAmogusEnjoyer	Harbingers (CEOI09_harbingers)	C++20	70 / 100	263 ms	131072 KiB

harbingers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

const int N = 100100;
vector<pair<int,int>> adj[N];
ll start[N];
ll speed[N];
ll depth[N];
ll dp[N];
int n;

void dfs(int u = 0,int p = -1) {
    for (auto &[v,w]: adj[u]) if (v != p) {
        depth[v] = depth[u] + w;
        dfs(v,u);
    }
}

struct line {
    ll m,q;
    ll eval(ll x) { return m * x + q; }
    double intersect(line &l) { return (double)(q - l.q) / (l.m - m); }  
};

line dq[N];
int dqsz=0;
vector<line> removed[N];

ll eval(ll x) {
    assert(dqsz!=0);
    int lo = 0, hi = dqsz;
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid + 1 == dqsz || dq[mid].intersect(dq[mid + 1]) >= x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }  
    return dq[lo].eval(x);
}

void dfs2(int u = 0,int p = -1) {
    if (u > 0) {
        dp[u] = eval(speed[u]) + start[u] + depth[u] * speed[u];
    }
    line cur{-depth[u],dp[u]};
    while(dqsz >= 2 && cur.intersect(dq[dqsz-1]) <= dq[dqsz-1].intersect(dq[dqsz - 2])) {
        removed[u].push_back(dq[dqsz-1]);
        dqsz--;
    }
    dq[dqsz++] = cur;
    for (auto &[v,w]: adj[u]) if (v != p) {
        dfs2(v,u);
    }
    assert(dq[dqsz - 1].m == cur.m && dq[dqsz - 1].q == cur.q);
    dqsz--;
    reverse(removed[u].begin(),removed[u].end());
    for (auto &l: removed[u])
        dq[dqsz++] = l;
}

void solve() {
    cin >> n;
    for (int u,v,w,i=1;i<n;i++) {
        cin >> u >> v >> w;
        --u,--v;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    for (int i = 1; i < n; i++) 
        cin >> start[i] >> speed[i];
    dfs();
    dfs2();
    for (int i = 1; i < n; i++) 
        cout << dp[i] << " ";
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    int testcases = 1;
    // cin >> testcases;
    for (int i = 1; i <= testcases; i++) 
        solve();

}

• Subtask 1: 70 / 100