제출 #1123526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123526		AverageAmogusEnjoyer	Harbingers (CEOI09_harbingers)	C++20	0 / 100	325 ms	20288 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];
line removed[N];
int remsz=0;
int dqsz=0;

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

int rem[N];

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[remsz++] = dq[dqsz-1];
        rem[u]++;
        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--;
    for (int i = remsz - rem[u]; i < remsz; i++) {
        dq[dqsz++] = removed[i];
    }
    remsz -= rem[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();
    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: 0 / 100