Submission #936866

#	Time	Username	Problem	Language	Result	Execution time	Memory
936866		idiotcomputer	Harbingers (CEOI09_harbingers)	C++11	100 / 100	114 ms	21012 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<int,int>
#define pb push_back
#define sz size
#define f first
#define s second 

const int mxN = 1e5;
int start[mxN];
int speed[mxN];
vector<pii> adj[mxN];

ll dp[mxN];
ll dist[mxN];
ll comp(int a, int b){
    if (dist[b] < dist[a]) swap(a,b);
    return (ll) ceil((double) (dp[b] - dp[a]) / (double) (dist[b] - dist[a]));
}

int alls = 0;
int all[mxN];

void dfs(int node, int p){
    dp[node] = 0;
    int r = alls-1;
    int l = -1;
    int curr;
    while (r - l > 1){
        curr = (r+l)/2;
        if (comp(all[curr],all[curr+1]) <= (ll) speed[node]){
            l = curr;
        } else {
            r = curr;
        }
    }

    if (l != r){
        dp[node] = dp[all[r]] + (dist[node] - dist[all[r]]) * (ll) speed[node] + (ll) start[node];
    }
    
    r = alls;
    l = 0;
    while (r - l > 1){
        curr = (l+r)/2;
        if (comp(all[curr],all[curr-1]) >= comp(all[curr],node)){
            r = curr;
        } else {
            l = curr;
        }
    }
    
    int prevl = all[r];
    int prevm = alls;
    all[r] = node;
    alls = r+1;
    
    for (pii next : adj[node]){
        if (next.f != p){
            dist[next.f] = dist[node] + next.s;
            dfs(next.f,node);
        }    
    }
    all[r] = prevl;
    alls = prevm;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    int a,b,d;
    for (int i =0; i < n-1; i++){
        cin >> a >> b >> d;
        a -= 1;
        b -= 1;
        adj[a].pb({b,d});
        adj[b].pb({a,d});
    }
    start[0] = 0;
    speed[0] = 0;
    for (int i =1; i < n; i++) cin >> start[i] >> speed[i];
    
    dist[0] = 0;
    dfs(0,-1);
    for (int i =1; i < n; i++){
        cout << dp[i] << " ";
    }
    cout << '\n';
    return 0;
}

• Subtask 1: 100 / 100