oj.uz

Submission #936866

# Submission time Handle Problem Language Result Execution time Memory
936866 2024-03-02T23:20:11 Z idiotcomputer Harbingers (CEOI09_harbingers) C++11
100 / 100
 114 ms 21012 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4596 KB Output is correct
2 Correct 2 ms 4788 KB Output is correct
3 Correct 40 ms 10480 KB Output is correct
4 Correct 67 ms 13376 KB Output is correct
5 Correct 62 ms 18000 KB Output is correct
6 Correct 75 ms 21012 KB Output is correct
7 Correct 39 ms 10408 KB Output is correct
8 Correct 113 ms 13680 KB Output is correct
9 Correct 114 ms 15700 KB Output is correct
10 Correct 110 ms 14800 KB Output is correct