Submission #210758

#	Time	Username	Problem	Language	Result	Execution time	Memory
210758		YouKnowWho	Harbingers (CEOI09_harbingers)	C++17	40 / 100	348 ms	65536 KiB

harbingers

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

#define ll long long
#define eb emplace_back
#define nl '\n'
#define deb(x) cerr << #x" = " << x << nl
#define in() ( { int a ; scanf("%d", &a); a; } )

const int N = 1e5 + 9;
const int mod = 1e9 + 7;

struct Line {
    int k; ll d;
    ll eval(int x) {
        return 1LL * k * x + d;
    }
};

struct LiChaoNode {
    Line line;
    int l, r;
    LiChaoNode(){line = Line({0, numeric_limits<long long>::max() / 2});l = 0, r = 0;}
    LiChaoNode(Line line) : line(line), l(0), r(0) {}
}t[9 * N];

int T;
vector<int> coord;
int upd(int pre, Line nw, int l, int r)
{
    int m = (l + r) / 2;
    int id = ++T;
    t[id].line = t[pre].line;
    bool lef = nw.eval(coord[l]) < t[id].line.eval(coord[l]);
    bool mid = nw.eval(coord[m]) < t[id].line.eval(coord[m]);
    if(mid) swap(t[id].line, nw);
    if(l == r) return id;
    if(lef != mid){
        if(!t[pre].l) t[id].l = ++T, t[T] = LiChaoNode(nw);
        else t[id].l = upd(t[pre].l, nw, l, m);
        t[id].r = t[pre].r;
    }
    else{
        if(!t[pre].r) t[id].r = ++T, t[T] = LiChaoNode(nw);
        else t[id].r = upd(t[pre].r, nw, m + 1, r);
        t[id].l = t[pre].l;
    }
    return id;
}

ll query(int cur, int x, int l, int r)
{
    ll val = t[cur].line.eval(x);
    int m = (l + r) / 2;
    if(l < r)
    {
        if(x <= coord[m] && t[cur].l) val = min(val, query(t[cur].l, x, l, m));
        if(x > coord[m] && t[cur].r) val = min(val, query(t[cur].r, x, m + 1, r));
    }
    return val;
}

struct PersistentLiChaoTree
{
    int L, R;
    vector<int> roots;
    PersistentLiChaoTree(){roots = {1}; T = 1;}
    PersistentLiChaoTree(int L, int R) : L(L), R(R) {
        T = 1;
        roots.push_back(1);
    }
    void add_line(Line line) {
        int root = upd(roots.back(), line, L, R);
        roots.push_back(root);
    }
    ll get(int i, int x) {
        return query(roots[i], x, L, R);
    }
}lt;

ll sum[N];
vector<pair<int, int>> g[N];
void dfs(int u, int pre = 0)
{
    for(auto x: g[u]){
        int v = x.first, d = x.second;
        if(v == pre) continue;
        sum[v] = sum[u] + d;
        dfs(v, u);
    }
}
ll ans[N];
int rev[N];
int p[N], s[N];
void yo(int u, int pre = 0)
{
    for(auto x: g[u]){
        int v = x.first;
        if(v == pre) continue;
        ans[v] = lt.get((int)lt.roots.size() - 1, p[v]) + sum[v] * p[v] + s[v];
        int sz = lt.roots.size();
        lt.add_line(Line({-sum[v], ans[v]}));
        yo(v, u);
        lt.roots.pop_back();
    }
}
int main()
{
        int n; cin >> n;
        for(int i = 1; i < n; i++){
            int u, v, d; cin >> u >> v >> d;
            g[u].eb(v, d);
            g[v].eb(u, d);
        }
        for(int i = 2; i <= n; i++) cin >> s[i] >> p[i], coord.eb(p[i]);
        sort(coord.begin(), coord.end());
        coord.erase(unique(coord.begin(), coord.end()), coord.end());
        dfs(1);
        T = 0;
        lt = PersistentLiChaoTree(0, coord.size() - 1);
        lt.add_line(Line({0, 0}));
        yo(1);
        for(int i = 2; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void yo(int, int)':
harbingers.cpp:102:27: warning: narrowing conversion of '- sum[v]' from 'long long int' to 'int' inside { } [-Wnarrowing]
         lt.add_line(Line({-sum[v], ans[v]}));
                           ^~~~~~~
harbingers.cpp:101:13: warning: unused variable 'sz' [-Wunused-variable]
         int sz = lt.roots.size();
             ^~

• Subtask 1: 40 / 100