제출 #420125

#제출 시각아이디문제언어결과실행 시간메모리
420125JerryLiu06Harbingers (CEOI09_harbingers)C++17
80 / 100
192 ms29664 KiB
#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[2 * 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]; int 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] << " "; }

컴파일 시 표준 에러 (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 |     }
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...