# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
130809 | 2019-07-16T06:08:08 Z | 임유진(#3171) | Harbingers (CEOI09_harbingers) | C++14 | 749 ms | 57560 KB |
#include <stdio.h> #include <vector> using namespace std; #define MAXN 100005 #define fi first #define se second typedef long long lint; typedef pair<lint, int> pli; lint S[MAXN], V[MAXN]; vector<pli> ed[MAXN]; pli par[20][MAXN]; int dep[MAXN]; lint ans[MAXN], dp[MAXN]; int link[20][MAXN]; lint dis(int x, int y) { //x is ancestor, y is child lint ans = 0ll; for(int i = 0; i < 20; i++) if((dep[y] - dep[x]) & (1 << i)) { ans += par[i][y].fi; y = par[i][y].se; } return ans; } void dfs(int x) { //printf("dfs(%d)\n", x); if(x == 1) for(int i = 0; i < 20; i++) link[i][1] = 1; else { int y = par[0][x].se; for(int i = 19; i >= 0; i--) if(dp[link[i][y]] >= V[x]) y = link[i][y]; y = link[0][y]; ans[x] = ans[y] + dis(y, x) * V[x] + S[x]; y = par[0][x].se; for(int i = 19; i >= 0; i--) if(ans[link[i][y]] + dis(link[i][y], x) * (dp[link[i][y]] + 1) > ans[x]) y = link[i][y]; y = link[0][y]; dp[x] = (ans[x] - ans[y]) / dis(y, x); y = par[0][x].se; for(int i = 19; i >= 0; i--) if(dp[link[i][y]] >= dp[x]) y = link[i][y]; link[0][x] = dp[y] >= dp[x] ? link[0][y] : y; for(int i = 1; i < 20; i++) link[i][x] = link[i - 1][link[i - 1][x]]; } //printf("x = %d, ans = %lld, dp = %lld\n", x, ans[x], dp[x]); for(auto a : ed[x]) if(a.se != par[0][x].se) { par[0][a.se] = make_pair(a.fi, x); for(int i = 1; i < 20; i++) par[i][a.se] = make_pair(par[i - 1][a.se].fi + par[i - 1][par[i - 1][a.se].se].fi, par[i - 1][par[i - 1][a.se].se].se); dep[a.se] = dep[x] + 1; dfs(a.se); } } int main() { int N; int u, v; lint c; scanf("%d", &N); for(int i = 0; i < N - 1; i++) { scanf("%d%d%lld", &u, &v, &c); ed[u].push_back(make_pair(c, v)); ed[v].push_back(make_pair(c, u)); } for(int i = 2; i <= N; i++) scanf("%lld%lld", S + i, V + i); dep[1] = 1; dfs(1); for(int i = 2; i <= N; i++) printf("%lld ", ans[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2940 KB | Output isn't correct |
2 | Incorrect | 12 ms | 4344 KB | Output isn't correct |
3 | Incorrect | 234 ms | 25180 KB | Output isn't correct |
4 | Runtime error | 372 ms | 36256 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
5 | Runtime error | 401 ms | 46972 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
6 | Runtime error | 510 ms | 57560 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
7 | Runtime error | 303 ms | 38384 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
8 | Runtime error | 749 ms | 54320 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
9 | Runtime error | 631 ms | 55280 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
10 | Runtime error | 637 ms | 54356 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |