제출 #968493

#제출 시각아이디문제언어결과실행 시간메모리
968493rxlfd314Harbingers (CEOI09_harbingers)C++17
0 / 100
5 ms4444 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define vt vector #define size(x) (int((x).size())) #define all(x) begin(x), end(x) #define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d)) #define FOR(a,b,c) REP(a,b,c,1) #define ROF(a,b,c) REP(a,b,c,-1) constexpr int mxN = 100005; int N; pair<ll, ll> lines[mxN]; vt<pair<int, int>> adj[mxN]; int intersection (pair<ll, ll> a, pair<ll, ll> b){ return (b.second-a.second)/(a.first-b.first); } ll eval(pair<ll, ll> line, int x) { return 1ll * line.first * x + line.second; } int depth[mxN], inter[mxN], lift[mxN][17], V[mxN], S[mxN]; ll ans[mxN]; void dfs(int i, int p) { int best = p; ROF(j, 16, 0) { int k = lift[best][j]; if (k && eval(lines[lift[k][0]], V[i]) > eval(lines[k], V[i])) { best = k; } } if (eval(lines[lift[best][0]], V[i]) > eval(lines[best], V[i])) best = lift[best][0]; if (i) ans[i] = 1ll*depth[i]*V[i] + S[i] - eval(lines[best], V[i]); lines[i] = {depth[i], -ans[i]}; best = p; ROF(j, 16, 0) { int k = lift[best][j]; if (k && intersection(lines[lift[k][0]], lines[k]) >= intersection(lines[k], lines[i])) { best = k; } } if (best && intersection(lines[lift[best][0]], lines[best]) >= intersection(lines[best], lines[i])) best = lift[best][0]; lift[i][0] = best; FOR(j, 1, 16) lift[i][j] = lift[lift[i][j-1]][j-1]; for (auto [j, v] : adj[i]) if (j != p) { depth[j] = depth[i] + v; dfs(j, i); } } signed main(){ #ifndef DEBUG freopen("harbingers.in", "r", stdin); freopen("harbingers.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif cin >> N; FOR(i, 2, N){ int a, b, c; cin >> a >> b >> c; adj[--a].push_back({--b, c}); adj[b].push_back({a, c}); } FOR(i, 1, N-1) cin >> S[i] >> V[i]; dfs(0, 0); FOR(i, 1, N-1){ cout << ans[i] << "\n "[i+1<N]; } }

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

harbingers.cpp: In function 'int main()':
harbingers.cpp:62:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   freopen("harbingers.in", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:63:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   freopen("harbingers.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...