Submission #924558

#TimeUsernameProblemLanguageResultExecution timeMemory
924558WhisperHarbingers (CEOI09_harbingers)C++17
20 / 100
118 ms65536 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using T = tuple<ll, ll, ll>; #define int long long #define Base 41 #define sz(a) (int)a.size() #define FOR(i, a, b) for ( int i = a ; i <= b ; i++ ) #define FORD(i, a, b) for (int i = b; i >= a; i --) #define REP(i, n) for (int i = 0; i < n; ++i) #define REPD(i, n) for (int i = n - 1; i >= 0; --i) #define all(x) x.begin() , x.end() #define pii pair<int , int> #define fi first #define se second #define Lg(x) 31 - __builtin_clz(x) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int MAX = 2e5 + 5; constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void setupIO(){ #define name "Whisper" //Phu Trong from Nguyen Tat Thanh High School for gifted student srand(time(NULL)); cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr); // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); cout << fixed << setprecision(10); } template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } vector<int> comp; struct Line{ int a, b; Line(): a(0), b(LINF){} Line(int _a, int _b):a(_a), b(_b){} int f(int x){ return a * comp[x] + b; } } f[4 * MAX]; stack<vector<pair<Line, int>>> st; int numNode; vector<pii> adj[MAX]; void addLine(int id, int l, int r, Line line, vector<pair<Line, int>> &state){ if (l == r){ if (line.f(l) < f[id].f(l)){ state.push_back({f[id], id}); f[id] = line; } return; } int mid = (l + r) >> 1; if (line.a > f[id].a){ state.push_back({f[id], id}); swap(line, f[id]); } if (line.f(mid) < f[id].f(mid)){ state.push_back({f[id], id}); swap(f[id], line); addLine(id << 1, l, mid, line, state); } else { addLine(id << 1 | 1, mid + 1, r, line, state); } } int query(int id, int l, int r, int x){ int ans = f[id].f(x); if (l == r) return ans; int mid = (l + r) >> 1; if (x <= mid) return min(ans, query(id << 1, l, mid, x)); return min(ans, query(id << 1 | 1, mid + 1, r, x)); } void addLine(int a, int b, vector<pair<Line, int>> &state){ addLine(1, 0, numNode - 1, Line(a, b), state); } int query(int x){ return query(1, 0, numNode - 1, x); } int dp[MAX], dis[MAX]; void rollback(){ if (st.empty()) return; vector<pair<Line, int>> state = st.top(); st.pop(); reverse(all(state)); for (auto&[line, id] : state){ f[id] = line; } } #define Find(x) lower_bound(all(comp), x) - comp.begin() int s[MAX], v[MAX]; void dfs(int u, int p){ if (u != 1) dp[u] = query(Find(-v[u])) + v[u] * dis[u] + s[u]; vector<pair<Line, int>> state; addLine(dis[u], dp[u], state); st.push(state); for (auto&[v, w] : adj[u]) if(v ^ p){ dis[v] = dis[u] + w; dfs(v, u); } rollback(); } void Whisper(){ cin >> numNode; for (int i = 1; i < numNode; ++i){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } comp.push_back(0); for (int i = 2; i <= numNode; ++i){ cin >> s[i] >> v[i]; comp.push_back(-v[i]); } sort(all(comp)); dfs(1, 0); for (int i = 2; i <= numNode; ++i) cout << dp[i] << " "; } signed main(){ setupIO(); int Test = 1; // cin >> Test; for ( int i = 1 ; i <= Test ; i++ ){ Whisper(); if (i < Test) cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...