Submission #936863

#	Time	Username	Problem	Language	Result	Execution time	Memory
936863		idiotcomputer	Harbingers (CEOI09_harbingers)	C++11	0 / 100	130 ms	65536 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]));
}

deque<int> all;
void dfs(int node, int p){
    dp[node] = 0;
    int r = all.sz()-1;
    int l = -1;
    int curr;
    while (r - l > 1){
        curr = (r+l)/2;
   //     cout << comp(all[curr],all[curr+1]) << "-" << all[curr] << " " << all[curr+1] << '\n';
        if (comp(all[curr],all[curr+1]) <= (ll) speed[node]){
            l = curr;
        } else {
            r = curr;
        }
    }
  /*  cout << node <<  " " << r << ": ";
    for (int i =0; i < all.sz(); i++){
        cout << all[i] << " ";
    }
    cout << "\n";*/
    if (l != r){
        dp[node] = dp[r] + (dist[node] - dist[r]) * (ll) speed[node] + (ll) start[node];
    }
    stack<int> rem;
    while (all.sz() > 1 && comp(all[all.sz()-1],all[all.sz()-2]) >= comp(all[all.sz()-1],node)){
       // cout <<  comp(all[all.sz()-1],all[all.sz()-2])  << " " << comp(all[all.sz()-1],node) << "\n";
        rem.push(all[all.sz()-1]);
        all.pop_back();
    }
    all.push_back(node);
    for (pii next : adj[node]){
        if (next.f != p){
            dist[next.f] = dist[node] + next.s;
            dfs(next.f,node);
        }    
    }
    all.pop_back();
    while (rem.sz()>0){
        all.push_back(rem.top());
        rem.pop();
    }
}


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: 0 / 100