Submission #1167166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167166		tuongll	Harbingers (CEOI09_harbingers)	C++20	100 / 100	64 ms	17036 KiB

harbingers

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <array>
#include <bitset>
#include <sstream>
#include <unordered_map>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) ((int)(a).size())
using namespace std;
const int mxn = 1e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 4e18;
struct line {
  ll a, b;
  ll operator()(ll x) const { return a * x + b; }
};
long double intersect(line l, line r){
  return (long double)(l.b - r.b) / (long double)(r.a - l.a);
}
line lines[mxn];
stack<tuple<int, int, line>> history;
int sz = 1; // lines are on [0, sz)
void add(line L){
  int pos = sz, l = 1, r = sz - 1;
  while(l <= r){
    int mid = (l + r) / 2;
    if (intersect(L, lines[mid - 1]) >= intersect(L, lines[mid]))
      pos = mid, r = mid - 1;
    else l = mid + 1;
  }
  history.emplace(pos, sz, lines[pos]);
  sz = pos + 1;
  lines[pos] = L;
}
void rollback(){
  int pos, old_sz; line l;
  tie(pos, old_sz, l) = history.top();
  history.pop();
  sz = old_sz;
  lines[pos] = l;
}
ll query(ll x){
  int pos = 0, l = 1, r = sz - 1;
  while(l <= r){
    int mid = (l + r) / 2;
    if (lines[mid - 1](x) >= lines[mid](x))
      pos = mid, l = mid + 1;
    else r = mid - 1;
  }
  return lines[pos](x);
}
int n;
ll prep[mxn], speed[mxn], dist[mxn], dp[mxn];
vector<pair<int, int>> g[mxn];
void dfs(int u, int pre, int pre_w){
  dist[u] = dist[pre] + pre_w;
  dp[u] = query(speed[u]) + prep[u] + speed[u] * dist[u];
  add({-dist[u], dp[u]});

  for (auto e : g[u]){
    int v, w; tie(v, w) = e;
    if (v == pre) continue;
    dfs(v, u, w);
  }
  rollback();
}
void solve(){
  cin >> n;
  for (int i = 1, u, v, w; i <= n - 1; ++i){
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  for (int i = 2; i <= n; ++i)
    cin >> prep[i] >> speed[i];
  for (auto e : g[1]){
    int u, w; tie(u, w) = e;
    dfs(u, 1, w);
  }
  for (int i = 2; i <= n; ++i)
    cout << dp[i] << ' ';
}
int main(){
  auto start = chrono::steady_clock::now();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  if (fopen("read.inp", "r")){
    freopen("read.inp", "r", stdin);
    freopen("write.out", "w", stdout);
  }
  int t = 1;
  // cin >> t;
  while(t--) solve();
  chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
  cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     freopen("read.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:105:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     freopen("write.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100