Submission #1266848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266848		luis_aqm	Harbingers (CEOI09_harbingers)	C++20	30 / 100	1097 ms	94836 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define NMAX 100005
#define INF 1e16
#define MOD 998244353
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

vector<pii> g[NMAX];
int s[NMAX], t[NMAX], dist[NMAX], dp[NMAX];
vector<int> hull;

double intersecx(int i, int j) {
    return 1.0 * (dp[i] - dp[j]) / (dist[i] - dist[j]);
}

void DFS(int v, int pai) {
    if(v != 1) {
        int l = 0, r = hull.size()-1;
        while(l < r) {
            int q = (r-l) / 3;
            int m1 = l+q, m2 = r-q;

            if(dp[hull[m1]] - dist[hull[m1]]*t[v] < dp[hull[m2]] - dist[hull[m2]]*t[v])
                r = m2-1;
            else l = m1+1;
        }

        dp[v] = dp[hull[r]] + (dist[v] - dist[hull[r]]) * t[v] + s[v];
    }

    stack<int> p;
    while(hull.size() > 1) {
        int j = hull.back(), k = hull[hull.size()-2];

        if(intersecx(v, j) < intersecx(j, k)) {
            p.push(j);
            hull.pop_back();
        }
        else break;
    }
    hull.push_back(v);

    for(auto [u, d] : g[v]) {
        if(u == pai) continue;

        dist[u] = dist[v] + d;
        DFS(u, v);
    }

    hull.pop_back();
    while(!p.empty()) {
        hull.push_back(p.top());
        p.pop();
    }
}

int32_t main(){ faster
    int n;
    cin>>n;

    for(int i = 1; i < n; i++) {
        int a, b, c;
        cin>>a>>b>>c;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    for(int i = 2; i <= n; i++) {
        cin>>s[i]>>t[i];
    }

    DFS(1, 0);

    for(int i = 2; i <= n; i++) {
        cout<<dp[i]<<" ";
    }
    cout<<"\n";
}
/*


*/

• Subtask 1: 30 / 100