oj.uz

답안 #130809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130809 2019-07-16T06:08:08 Z 임유진(#3171) Harbingers (CEOI09_harbingers) C++14
0 / 100
 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

harbingers.cpp: In function 'int main()':
harbingers.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
harbingers.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 2; i <= N; i++) scanf("%lld%lld", S + i, V + i);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 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)