Submission #479783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479783	2021-10-13T05:52:57 Z	jli12345	Harbingers (CEOI09_harbingers)	C++14	100 / 100	159 ms	21188 KB

harbingers

#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

typedef long long ll;

#define f first
#define s second

int N;

vector< pair<int, ll> > edges[101000];
pair<ll, ll> city[100100]; // w, t

ll dist[100100], dp[100100];
int convex[100100];
int pos = 0;

ll m(int ind){
    return -dist[ind];
}

ll b(int ind){
    return dp[ind];
}

ll val(int j, int i){
    return m(j)*city[i].s+b(j);
}

ll add(int ind){
    return dist[ind]*city[ind].s+city[ind].f;
}

ll best(int node){
    if (node == 1) return 0;
    int l = 1, r = pos;
    while (l != r){
        int mid = (l+r+1)/2;
        if (val(convex[mid], node) >= val(convex[mid-1], node)){
            r = mid-1;
        } else {
            l = mid;
        }
    }
    /*
    if (node == 3)
        cout << "best:" << l << " " << val(convex[l], node) << " " << add(node) << "\n";
    */
    return val(convex[l], node)+add(node);
}

long double intersect(int aa, int bb){
    return (long double)(b(aa)-b(bb))/(m(bb)-m(aa));
}

pair<int, ll> insert(int node){ //returns the index of insertion and previous value at that insertion
    if (node == 1){
        convex[1] = 1;
        pos = 1;
        return {1, 0};
    }
    int l = 1, r = pos;
    while (l != r){
        int mid = (l+r+1)/2;
        if (intersect(node, convex[mid]) >= intersect(convex[mid], convex[mid-1])){
            l = mid;
        } else {
            r = mid-1;
        }
    }
    ll pre = convex[l+1];
    convex[l+1] = node;
    pos = l+1;
    return {l+1, pre};
}

void dfs(int node, int pa = 0){
    dp[node] = best(node);
    int prevlen = pos;
    pair<int, ll> pref = insert(node);
    /*
    if (node == 3){
        cout << pos << ": ";
        for (int i = 1; i <= pos; i++){
            cout << m(convex[i]) << " " << b(convex[i]) << "\n";
        }
        cout << "\n";
    }*/
    for (pair<int, int> nx : edges[node]){
        if (nx.f == pa)
            continue;    
        dist[nx.f] = dist[node]+nx.s;
        dfs(nx.f, node);
    }
    convex[pref.f] = pref.s;
    pos = prevlen;
}

int main(){
    fastIO();
    cin >> N;
    for (int i = 1; i < N; i++){
        int a, b, c; cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    for (int i = 1; i < N; i++){
        cin >> city[i+1].f >> city[i+1].s;
    }
    dfs(1, 0);
    for (int i = 2; i <= N; i++) cout << dp[i] << " ";
    cout << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2636 KB	Output is correct
2	Correct	4 ms	3148 KB	Output is correct
3	Correct	58 ms	10400 KB	Output is correct
4	Correct	95 ms	14196 KB	Output is correct
5	Correct	94 ms	17708 KB	Output is correct
6	Correct	118 ms	21188 KB	Output is correct
7	Correct	71 ms	11396 KB	Output is correct
8	Correct	153 ms	16168 KB	Output is correct
9	Correct	159 ms	17752 KB	Output is correct
10	Correct	131 ms	16596 KB	Output is correct