oj.uz

Submission #968496

# Submission time Handle Problem Language Result Execution time Memory
968496 2024-04-23T13:47:32 Z rxlfd314 Harbingers (CEOI09_harbingers) C++17
100 / 100
 140 ms 25088 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
 
constexpr int mxN = 100005;
int N;
pair<ll, ll> lines[mxN];
vt<pair<int, int>> adj[mxN];
  
int intersection (pair<ll, ll> a, pair<ll, ll> b){
  return (b.second-a.second)/(a.first-b.first);
}
 
ll eval(pair<ll, ll> line, int x) {
  return 1ll * line.first * x + line.second;
}
 
int depth[mxN], inter[mxN], lift[mxN][17], V[mxN], S[mxN];
ll ans[mxN];
void dfs(int i, int p) {
  int best = p;
  ROF(j, 16, 0) {
    int k = lift[best][j];
    if (k && eval(lines[lift[k][0]], V[i]) > eval(lines[k], V[i])) {
      best = k;
    }
  }
  if (eval(lines[lift[best][0]], V[i]) > eval(lines[best], V[i]))
    best = lift[best][0];
  if (i)
    ans[i] = 1ll*depth[i]*V[i] + S[i] - eval(lines[best], V[i]);
  lines[i] = {depth[i], -ans[i]};
  best = p;
  ROF(j, 16, 0) {
    int k = lift[best][j];
    if (k && intersection(lines[lift[k][0]], lines[k]) >= intersection(lines[k], lines[i])) {
      best = k;
    }
  }
  if (best && intersection(lines[lift[best][0]], lines[best]) >= intersection(lines[best], lines[i]))
    best = lift[best][0];
  lift[i][0] = best;
  FOR(j, 1, 16)
    lift[i][j] = lift[lift[i][j-1]][j-1];
  for (auto [j, v] : adj[i])
    if (j != p) {
      depth[j] = depth[i] + v;
      dfs(j, i);
    }
}
 
signed main(){
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N;
  FOR(i, 2, N){
    int a, b, c;
    cin >> a >> b >> c;
    adj[--a].push_back({--b, c});
    adj[b].push_back({a, c});
  }
  FOR(i, 1, N-1)
    cin >> S[i] >> V[i];
  dfs(0, 0);
  FOR(i, 1, N-1){
    cout << ans[i] << "\n "[i+1<N];
  }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 43 ms 13800 KB Output is correct
4 Correct 64 ms 18004 KB Output is correct
5 Correct 64 ms 22608 KB Output is correct
6 Correct 80 ms 25088 KB Output is correct
7 Correct 54 ms 15700 KB Output is correct
8 Correct 122 ms 21052 KB Output is correct
9 Correct 140 ms 22612 KB Output is correct
10 Correct 109 ms 21708 KB Output is correct