oj.uz

Submission #130840

# Submission time Handle Problem Language Result Execution time Memory
130840 2019-07-16T06:57:59 Z 임유진(#3171) Harbingers (CEOI09_harbingers) C++14
100 / 100
 283 ms 24176 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;
typedef pair<int, int> pii;

int S[MAXN], V[MAXN];
vector<pii> ed[MAXN];
pii par[MAXN];
lint ans[MAXN], dp[MAXN];
pii link[17][MAXN];
vector<int> sta;

int main() {
	int N;
	int u, v, c;
	int x, y;
	int dis;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; i++) {
		scanf("%d%d%d", &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("%d%d", S + i, V + i);

	par[1] = make_pair(0, 1);
	for(int i = 0; i < 17; i++) link[i][1] = make_pair(0ll, 1);

	sta.push_back(1);
	while(!sta.empty()) {
		//printf("dfs(%d)\n", x);
		x = sta.back();
		sta.pop_back();
		if(x != 1) {
			y = par[x].se;
			dis = par[x].fi;
			for(int i = 16; i >= 0; i--) if(dp[link[i][y].se] >= V[x]) {
				dis += link[i][y].fi;
				y = link[i][y].se;
			}
			if(dp[y] >= V[x]) {
				dis += link[0][y].fi;
				y = link[0][y].se;
			}
			ans[x] = ans[y] + lint(dis) * V[x] + S[x];

			y = par[x].se;
			dis = par[x].fi;
			for(int i = 16; i >= 0; i--) if(ans[link[i][y].se] + (dis + link[i][y].fi) * (dp[link[i][y].se] + 1) > ans[x]) {
				dis += link[i][y].fi;
				y = link[i][y].se;
			}
			//printf("y = %d\n", y);
			if(ans[y] + dis * (dp[y] + 1) > ans[x]) {
				dis += link[0][y].fi;
				y = link[0][y].se;
			}
			dp[x] = (ans[x] - ans[y]) / dis;

			y = par[x].se;
			dis = par[x].fi;
			for(int i = 16; i >= 0; i--) if(dp[link[i][y].se] >= dp[x]) {
				dis += link[i][y].fi;
				y = link[i][y].se;
			}
			link[0][x] = dp[y] >= dp[x] ? make_pair(dis + link[0][y].fi, link[0][y].se) : make_pair(dis, y);
			for(int i = 1; i < 17; i++)
				link[i][x] = make_pair(link[i - 1][link[i - 1][x].se].fi + link[i - 1][x].fi, link[i - 1][link[i - 1][x].se].se);
		}
		//printf("x = %d, ans = %lld, dp = %lld, link = %d\n", x, ans[x], dp[x], link[0][x]);

		for(auto a : ed[x]) if(a.se != par[x].se) {
			par[a.se] = make_pair(a.fi, x);
			sta.push_back(a.se);
		}
		ed[x].clear();
	}

	for(int i = 2; i <= N; i++) printf("%lld ", ans[i]);
	return 0;
}

Compilation message

harbingers.cpp: In function 'int main()':
harbingers.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
harbingers.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:33: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("%d%d", S + i, V + i);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 7 ms 3320 KB Output is correct
3 Correct 75 ms 11228 KB Output is correct
4 Correct 114 ms 15296 KB Output is correct
5 Correct 148 ms 19232 KB Output is correct
6 Correct 190 ms 23132 KB Output is correct
7 Correct 121 ms 17144 KB Output is correct
8 Correct 283 ms 23924 KB Output is correct
9 Correct 242 ms 24176 KB Output is correct
10 Correct 226 ms 23968 KB Output is correct