Submission #1265637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265637		yazan	Harbingers (CEOI09_harbingers)	C++20	50 / 100	150 ms	91832 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e9;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;

struct Line{
    ll a, b;
    Line(){}
    Line(ll A, ll B){
        a = A, b = B;
    }
    ll val(ll x){
        return a * x + b;
    }
}emp(0, 0);

struct node{
    Line line;
    node *left, *right;
    node(){
        left = NULL, right = NULL;
        line = Line();
    }
    node(Line L){
        line = L;
        left = NULL, right = NULL;
    }
};

#define md (s+e)/2

void Upd(int s, int e, node *prev, node* &cur, Line line){
    if(prev == NULL){
        cur->line = line;
        return;
    }
    bool Left = prev->line.val(s) < line.val(s);
    bool Middle = prev->line.val(md + 1) < line.val(md + 1);
    bool Right = prev->line.val(e) < line.val(e);
    cur->line = prev->line;
    cur->left = prev->left, cur->right = prev->right;
    if(Left == Right){
        if(Left){
            cur->line = line;
        }
    }
    else if(Middle == Right){
        if(Right){
            swap(line, cur->line);
        }
        cur->left = new node();
        Upd(s, md, prev->left, cur->left, line);
    }
    else if(Left == Middle){
        if(Left){
            swap(line, cur->line);
        }
        cur->right = new node();
        Upd(md + 1, e, prev->right, cur->right, line);
    }
}

Line Get(int s, int e, node *cur, ll x){
    if(cur == NULL || e < x || s > x){
        return emp;
    }
    Line Line1 = Get(s, md, cur->left, x);
    Line Line2 = Get(md + 1, e, cur->right, x);
    Line ret = cur->line;
    if(ret.val(x) < Line1.val(x))ret = Line1;
    if(ret.val(x) < Line2.val(x))ret = Line2;
    return ret;
}

node *root[M];
vector < pair <int,int> > adj[M];
ll n, s[M], v[M], dist[M], dp[M];

// min j: dp[i] = dp[j] + -dist[j] * v[i] + dist[i] * v[i] + s[i]

void Dfs(int node, int p){
    dp[node] = -Get(0, inf, root[p], v[node]).val(v[node]) + dist[node] * v[node] + s[node];
    Upd(0, inf, root[p], root[node], Line(dist[node], -dp[node]));

    for(auto [i, d] : adj[node]) if(i != p){
        dist[i] = dist[node] + d;
        Dfs(i, node);
    }
}

void Dividers(int _){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int x, y, c;
        cin >> x >> y >> c;
        adj[x].pb({y, c});
        adj[y].pb({x, c});
    }
    for(int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
    
    for (int i = 0; i <= n; i++) root[i] = new node();
    Upd(0, inf, NULL, root[0], emp);
    Dfs(1, 0);

    for(int i = 2; i <= n; ++i) cout << dp[i] << " ";
    cout << endl;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) Dividers(t);

    return 0;
}

• Subtask 1: 50 / 100