Submission #1235324

#TimeUsernameProblemLanguageResultExecution timeMemory
1235324blackslexHarbingers (CEOI09_harbingers)C++20
0 / 100
78 ms19272 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; const int N = 1e5 + 5; int n, x, y, z, s[N], t[N], sz; ll dp[N]; vector<pii> v[N]; struct line { ll m, c; line() : m(0), c(0) {} line(ll m, ll c) : m(m), c(c) {} ll get (ll x) { return m * x + c; } friend ld operator * (const line &l1, const line &l2) { return 1.l * (l2.c - l1.c) / 1.l * (l1.m - l2.m); } } sk[N]; int add (line _l) { if (sz < 2) return sz; if (_l * sk[sz - 1] >= sk[sz - 1] * sk[sz - 2]) return sz; int l = 1, r = sz - 1; while (l < r) { int mid = (l + r) >> 1; if (_l * sk[mid] >= sk[mid] * sk[mid - 1]) r = mid; else l = mid + 1; } return l; } ll qr (ll x) { int l = 0, r = sz - 1; while (l < r) { int mid = (l + r) >> 1; if (sk[mid] * sk[mid + 1] >= x) r = mid; else l = mid + 1; } return sk[l].get(x); } void dfs (int cur, int par, ll dist){ if (cur != 1) { dp[cur] = qr(t[cur]) + s[cur] + dist * t[cur]; } line l(-dist, dp[cur]); int kk = add(l); int csz = sz, ccsz = kk; auto lk = sk[kk]; sk[sz++] = l; // hull.add(-dist, dp[cur]); for (auto &[x, y]: v[cur]) { if (par == x) continue; dfs(x, cur, dist + y); } sk[ccsz] = lk; sz = csz; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d %d %d", &x, &y, &z); v[x].emplace_back(y, z); v[y].emplace_back(x, z); } for (int i = 2; i <= n; i++) scanf("%d %d", &s[i], &t[i]); dp[1] = 0; dfs(1, 0, 0); for (int i = 2; i <= n; i++) printf("%lld ", dp[i]); }

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
harbingers.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:72:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     for (int i = 2; i <= n; i++) scanf("%d %d", &s[i], &t[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...