제출 #973820

#제출 시각아이디문제언어결과실행 시간메모리
973820duckindogHarbingers (CEOI09_harbingers)C++17
0 / 100
87 ms25172 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; const int N = 100'000 + 1; int n; vector<pair<int, int>> ad[N]; int s[N], velocity[N]; int d[N]; struct Line { long long a, b; double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); } }; struct CHT { int top; array<Line, N> hull; array<pair<int, Line>, N> save; void add(Line line, int u) { int preTop = top; int l = 2, r = top; top += 1; while (l <= r) { int mid = l + r >> 1; if (hull[mid].x(hull[mid - 1]) >= hull[mid].x(line)) l = (top = mid) + 1; else r = mid - 1; } save[u] = {preTop, hull[top]}; hull[top] = line; } long long query(int u) { auto cal = [&](int it) { return hull[it].a * velocity[u] + hull[it].b + 1ll * d[u] * velocity[u] + s[u]; }; int l = 1, r = top - 1, it = 1; while (l <= r) { int mid = l + r >> 1; if (cal(mid) >= cal(mid + 1)) l = it = mid + 1; else r = mid - 1; } return cal(it); } } convex; long long dp[N]; void dfs(int u, int p = 0) { auto& ret = dp[u]; ret = min(ret, convex.query(u)); convex.add({-d[u], ret}, u); for (const auto& [v, w] : ad[u]) { if (v == p) continue; d[v] = d[u] + w; dfs(v, u); } auto[top, line] = convex.save[u]; convex.hull[convex.top] = line; convex.top = top; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 2; i <= n; ++i) { int u, v, w; cin >> u >> v >> w; ad[u].push_back({v, w}); ad[v].push_back({u, w}); } for (int i = 2; i <= n; ++i) cin >> s[i] >> velocity[i]; memset(dp, 40, sizeof dp); dfs(1); for (int i = 2; i <= n; ++i) cout << dp[i] << " \n"[i == n]; cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n"; }

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

harbingers.cpp:15:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 |   double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
      |                  ^~~~
harbingers.cpp: In member function 'void CHT::add(Line, int)':
harbingers.cpp:26:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |       int mid = l + r >> 1;
      |                 ~~^~~
harbingers.cpp: In member function 'long long int CHT::query(int)':
harbingers.cpp:40:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |       int mid = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...