제출 #978646

#제출 시각아이디문제언어결과실행 시간메모리
978646raspyHarbingers (CEOI09_harbingers)C++14
40 / 100
1088 ms33620 KiB
#include <iostream> #include <vector> #include <algorithm> #define EPS 0.0000001 #define inf 1'000'000'000'000'000 #define int long long using namespace std; typedef pair<int, int> ii; struct ln { int m, c; double p; }; vector<ii> graf[200005]; ii hr[200005]; // c, m vector<ln> ch; int dp[200005]; double getX(int m1, int c1, int m2, int c2) { return (double)(c1- c2)/(m2- m1); } vector<ln> dodaj(int m, int c) { vector<ln> iz; double p = -inf; while (!ch.empty()) { p = getX(m, c, ch.back().m, ch.back().c); if (p < ch.back().p-EPS) { iz.push_back(ch.back()); ch.pop_back(); } else break; } ch.push_back({m, c, p}); return iz; } int getBestY(int x) { int k = 0; int L = 0, R = ch.size()- 1; while (L <= R) { int mid = (L+R) >> 1; if (ch[mid].p <= x+EPS) k = mid, L = mid+1; else R = mid-1; } return ch[k].m*x + ch[k].c; } void dfs(int u = 1, int gl = 0, int p = -1) { int zv = gl*hr[u].second+hr[u].first; if (!ch.empty()) zv += getBestY(hr[u].second); dp[u] = zv; vector<ln> iz = dodaj(-gl, zv); for (auto [v, d] : graf[u]) if (v != p) dfs(v, gl+d, u); ch.pop_back(); for (auto l : iz) ch.push_back(l); } int32_t main() { int n; cin >> n; for (int i = 0; i < n-1; i++) { int u, v, d; cin >> u >> v >> d; graf[u].push_back({v, d}); graf[v].push_back({u, d}); } for (int i = 1; i < n; i++) cin >> hr[i+1].first >> hr[i+1].second; dfs(); for (int i = 2; i <= n; i++) cout << dp[i] << " "; cout << "\n"; return 0; }

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

harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:65:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for (auto [v, d] : graf[u])
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...