Submission #1123542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123542		AverageAmogusEnjoyer	Harbingers (CEOI09_harbingers)	C++20	20 / 100	1096 ms	22272 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;

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); }  
};

int sz[N],head[N],par[N];
vector<line> containers[N];
void dfs(int u = 0,int p = -1) {
    sz[u] = 1;
    par[u] = p;
    for (auto &[v,w]: adj[u]) if (v != p) {
        depth[v] = depth[u] + w;
        dfs(v,u);
        sz[u] += sz[v];
    }
    sort(adj[u].begin(),adj[u].end(),[&](auto &x,auto &y) {
        return sz[x.first] > sz[y.first];
    });
}
void dfs2(int u = 0,int p = -1,int h = 0) {
    bool g = 1;
    head[u] = h;
    for (auto &[v,w]: adj[u]) if (v != p) {
        if (!g) {
            dfs2(v,u,h);
            g = 0;
        } else {
            dfs2(v,u,v);
        }
    }
}
ll eval(vector<line> &dq,ll x) {
    if (dq.empty()) 
        return 1LL << 60;
    int lo = 0, hi = dq.size();
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid + 1 == dq.size() || dq[mid].intersect(dq[mid + 1]) >= x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }  
    return dq[lo].eval(x);
}
void dfs3(int u = 0,int p = -1) {
    if (u > 0) {
        int uu = u;
        dp[u] = 1LL << 60;
        while(uu != -1) {
            uu = head[uu];
            cmin(dp[u],eval(containers[uu],speed[u]));
            uu = par[uu];
        }
        dp[u] += start[u] + depth[u] * speed[u];
    }
    line cur{-depth[u],dp[u]};
    auto &dq = containers[head[u]];
    while(dq.size() >= 2 && cur.intersect(dq[dq.size() - 1]) <= dq[dq.size() - 1].intersect(dq[dq.size() - 2])) {
        dq.pop_back();
    }
    dq.push_back(cur);
    reverse(adj[u].begin(),adj[u].end());
    for (auto &[v,w]: adj[u]) if (v != p) 
        dfs3(v,u);
}

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();
    dfs3();
    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: 20 / 100