제출 #400182

#제출 시각아이디문제언어결과실행 시간메모리
400182hltkHarbingers (CEOI09_harbingers)C++17
50 / 100
1089 ms17572 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> int bins(int l, int r, T f) { while (l < r) { int m = (l + r) / 2; f(m) ? r = m : l = m + 1; } return l; } const long INF = 1e18; int n, s[100100], t[100100]; long dp[100100]; vector<pair<int, int>> g[100100]; struct Line { long m, c; long operator()(long x) { return m * x + c; } } cht[100100]; long intersect(Line a, Line b) { long num = b.c - a.c, dem = a.m - b.m; return num / dem - ((num ^ dem) < 0 && num % dem); } void dfs(int u, int p, int ed, long cd) { if (u != 1) { dp[u] = cd * t[u] + s[u] - cht[bins(0, ed - 1, [&](int m) { return cht[m](t[u]) > cht[m + 1](t[u]); })](t[u]); Line l{cd, -dp[u]}; int ned = 0; while (ned + 1 < ed) { if (intersect(cht[ned], cht[ned + 1]) < intersect(cht[ned + 1], l)) { ned++; } else break; } ned++; swap(cht[ned], l); // bins(0, ed - 1, [&](int m) { // return intersect(cht[m], cht[m + 1]) >= intersect(cht[m + 1], l); // }); for (auto [v, d] : g[u]) { if (v == p) continue; dfs(v, u, ned + 1, cd + d); } swap(cht[ned], l); } else { for (auto [v, d] : g[u]) { if (v == p) continue; dfs(v, u, ed, cd + d); } } } int main() { scanf("%d", &n); for (int i = 1, u, v, d; i <= n - 1; ++i) { scanf("%d %d %d", &u, &v, &d); g[u].emplace_back(v, d); g[v].emplace_back(u, d); } for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i); dfs(1, -1, 1, 0); for (int i = 2; i <= n; ++i) printf("%ld%c", dp[i], i == n ? '\n' : ' '); } // f_j(x) := -dp[j] + dep[j] * x // dp[j] + (d - x) t_i + s_i // = dp[j] - x * t_i + d * t_i + s_i // = -f_j(t_i) + d * t_i + s_i

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp: In function 'int main()':
harbingers.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d %d %d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:59:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...