oj.uz

답안 #130816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130816 2019-07-16T06:18:55 Z 김세빈(#3168) Harbingers (CEOI09_harbingers) C++14
80 / 100
 286 ms 34552 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

vector <pll> T[101010];
ll P[101010][22];
pll S[101010];
ll D[101010], A[101010], B[101010];
ll n;

void insert(ll p, ll r, ll a, ll b)
{
	ll i, a1, a2, b1, b2;
	
	S[p] = pll(a, b);
	
	for(i=16; i>=0; i--){
		if(P[r][i] == P[P[r][i]][0]) continue;
		tie(a1, b1) = S[P[r][i]];
		tie(a2, b2) = S[P[P[r][i]][0]];
		if((ld)(b2 - b) / (a - a2) < (ld)(b2 - b1) / (a1 - a2)){
			r = P[P[r][i]][0];
		}
	}
	
	if(r != P[r][0]){
		tie(a1, b1) = S[r];
		tie(a2, b2) = S[P[r][0]];
		if((ld)(b2 - b) / (a - a2) < (ld)(b2 - b1) / (a1 - a2)){
			r = P[r][0];
		}
	}
	
	P[p][0] = r;
	for(i=1; i<=16; i++){
		P[p][i] = P[P[p][i - 1]][i - 1];
	}
}

ll getval(ll p, ll x)
{
	ll i, ret, a1, a2, b1, b2;
	
	ret = S[p].first * x + S[p].second;
	
	for(i=16; i>=0; i--){
		if(P[p][i] == P[P[p][i]][0]) continue;
		tie(a1, b1) = S[P[p][i]];
		tie(a2, b2) = S[P[P[p][i]][0]];
		if(a1 * x + b1 > a2 * x + b2){
			p = P[p][i];
		}
	}
	
	p = P[p][0];
	ret = min(ret, S[p].first * x + S[p].second);
	
	return ret;
}

void dfs(ll p, ll r, ll d)
{
	D[p] = A[p] + B[p] * d + getval(r, B[p]);
	insert(p, r, -d, D[p]);
	
	for(pll &t: T[p]){
		if(t.first != r){
			dfs(t.first, p, d + t.second);
		}
	}
}

int main()
{
	ll i, u, v, c;
	
	scanf("%lld", &n);
	
	for(i=1; i<n; i++){
		scanf("%lld%lld%lld", &u, &v, &c);
		T[u].emplace_back(v, c);
		T[v].emplace_back(u, c);
	}
	
	for(i=2; i<=n; i++){
		scanf("%lld%lld", A + i, B + i);
	}
	
	dfs(1, 0, 1);
	
	for(i=2; i<=n; i++){
		printf("%lld ", D[i]);
	}
	
	printf("\n");
	
	return 0;
}

Compilation message

harbingers.cpp: In function 'int main()':
harbingers.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
harbingers.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 8 ms 3576 KB Output is correct
3 Correct 93 ms 15836 KB Output is correct
4 Correct 142 ms 22108 KB Output is correct
5 Correct 173 ms 28368 KB Output is correct
6 Runtime error 196 ms 34552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 115 ms 22824 KB Output is correct
8 Correct 286 ms 32284 KB Output is correct
9 Runtime error 278 ms 33036 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Correct 250 ms 32112 KB Output is correct