Submission #420122

#	Time	Username	Problem	Language	Result	Execution time	Memory
420122		JerryLiu06	Harbingers (CEOI09_harbingers)	C++17	80 / 100	194 ms	35916 KiB

harbingers

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

// Description: Li Chao Segment Tree. You can add lines of the form kx + m, and query maximum
// values at points x. *Useful for dynamic programming (CHT)* Time: O(lg N)

struct Line {
    ll M, C; Line() { M = 0, C = INF; } Line(ll _M, ll _C) { M = _M; C = _C; }

    ll operator()(ll X) { return M * X + C; }
};

vl allV;

struct LiChaoSegTree {
    Line tree[4 * MX]; stack<pair<int, Line>> stck;

    void update(int x, int l, int r, Line line) { int mid = (l + r) / 2;
        bool L = tree[x](allV[l]) > line(allV[l]); bool M = tree[x](allV[mid]) > line(allV[mid]); bool R = tree[x](allV[r]) > line(allV[r]);

        if (L == R) { if (L) { swap(tree[x], line); stck.push({x, line}); } return ; }

        if (L == M) { if (L) { swap(tree[x], line); stck.push({x, line}); } update(2 * x + 1, mid + 1, r, line); }
        if (M == R) { if (R) { swap(tree[x], line); stck.push({x, line}); } update(2 * x, l, mid, line); }
    }
    ll query(int x, int l, int r, int pos) {
        int mid = (l + r) / 2; if (l == r) return tree[x](allV[pos]);
        
        if (pos <= mid) return min(tree[x](allV[pos]), query(2 * x, l, mid, pos));
        if (pos > mid) return min(tree[x](allV[pos]), query(2 * x + 1, mid + 1, r, pos));
    }
    void rollback(int prevSz) {
        while (sz(stck) > prevSz) { 
            tree[stck.top().f] = stck.top().s; stck.pop(); 
        }
    } 
};

int N; vpi adj[MX]; ll S[MX], V[MX]; ll DP[MX]; LiChaoSegTree LC;

void DFS(int X, int P, ll depth) {
    if (X > 1) {
        DP[X] = LC.query(1, 0, sz(allV) - 1, lb(all(allV), V[X]) - allV.bg()) + V[X] * depth + S[X];
    }

    int cur = sz(LC.stck); LC.update(1, 0, sz(allV) - 1, Line(-depth, DP[X]));

    EACH(Y, adj[X]) if (Y.f != P) DFS(Y.f, X, depth + Y.s);
    
    LC.rollback(cur);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; F0R(i, N - 1) { int A, B, L; cin >> A >> B >> L; adj[A].pb({B, L}), adj[B].pb({A, L}); }

    FOR(i, 2, N + 1) cin >> S[i] >> V[i], allV.pb(V[i]);

    sor(allV); allV.erase(unique(all(allV)), allV.end()); 

    DFS(1, 0, 0); FOR(i, 2, N + 1) cout << DP[i] << " ";
}

Compilation message (stderr)

harbingers.cpp: In member function 'll LiChaoSegTree::query(int, int, int, int)':
harbingers.cpp:76:5: warning: control reaches end of non-void function [-Wreturn-type]
   76 |     }
      |     ^

• Subtask 1: 80 / 100