제출 #400034

#제출 시각아이디문제언어결과실행 시간메모리
400034hltkHarbingers (CEOI09_harbingers)C++17
80 / 100
1087 ms25172 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("sse4.2,avx2") #include <bits/stdc++.h> using namespace std; const long INF = 1e18; int n, s[100100], t[100100]; vector<pair<int, int>> g[100100]; int sz[100100]; void dfs_sz(int u) { sz[u] = 1; for (auto &p : g[u]) { int v = p.first; g[v].erase(find_if(g[v].begin(), g[v].end(), [&](auto a) { return a.first == u; })); dfs_sz(v); if (sz[v] > sz[g[u][0].first]) swap(p, g[u][0]); sz[u] += sz[v]; } } long dp[100100]; struct Line { long m, c; long operator()(long x) { return m * x + c; } }; 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); } vector<pair<long, Line>> cht{{-INF, {0, 0}}}; vector<Line> st; long query(long x) { long ret = prev(lower_bound(cht.begin(), cht.end(), pair{x, Line{}}, [&](auto a, auto b) { return a.first < b.first; }))->second(x); for (auto u : st) ret = max(ret, u(x)); return ret; } void dfs(int u, long cd, bool heavy) { vector<Line> popped; if (u != 1) { dp[u] = -query(t[u]) + cd * t[u] + s[u]; auto l = Line{cd, -dp[u]}; if (heavy) { while ((int) cht.size() >= 2) { auto a = cht[cht.size() - 2].second; auto b = cht[cht.size() - 1].second; if (intersect(a, b) >= intersect(b, l)) { popped.push_back(cht.back().second); cht.pop_back(); } else break; } cht.emplace_back(intersect(cht.back().second, l), l); } else { st.push_back(l); } } for (auto [v, d] : g[u]) { dfs(v, cd + d, v == g[u][0].first); } if (u != 1) { if (heavy) { cht.pop_back(); while (!popped.empty()) { cht.emplace_back(intersect(cht.back().second, popped.back()), popped.back()); popped.pop_back(); } } else { st.pop_back(); } } } 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_sz(1); dfs(1, 0, 1); 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:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%d %d %d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:80:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...