/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 9000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT "C"
#define MOD 1000000007
using namespace std;
// https://oj.vnoi.info/problem/harbinge
int n;
vector <pii> adj[nmax];
ll h[nmax];
int s[nmax], v[nmax];
ll f[nmax];
vector <int> node;
struct Line
{
ll a, b;
Line(ll a = 0, ll b = 0) : a(a), b(b) {}
ll getValue(ll x)
{
return a * x + b;
}
};
double slope(Line A, Line B)
{
return (double) (A.b - B.b) / (B.a - A.a);
}
Line Stack[nmax];
int stackSize = 0;
ll Get(ll x)
{
if(stackSize == 1)
{
return Stack[1].getValue(x);
}
int l = 1, r = stackSize - 1, res = stackSize;
while(l <= r)
{
int mid = (l + r) >> 1;
if(slope(Stack[mid], Stack[mid + 1]) >= x)
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return Stack[res].getValue(x);
}
int findPos(Line tmp)
{
if(stackSize == 1) return 1;
int l = 1, r = stackSize - 1, res = stackSize;
while(l <= r)
{
int mid = (l + r) >> 1;
if(slope(Stack[mid], Stack[mid + 1]) >= slope(tmp, Stack[mid + 1]))
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
void dfs(int u, int p)
{
if(u > 1)
{
// f[u] = OO;
// for(int x : node)
// f[u] = min(f[u], s[u] + v[u] * (h[u] - h[x]) + f[x]);
f[u] = Get(v[u]) + s[u] + 1ll * v[u] * h[u];
}
Line tmp(-h[u], f[u]);
int pos = findPos(tmp) + 1;
int saveSize = stackSize;
Line saveLine = Stack[pos];
Stack[pos] = tmp;
stackSize = pos;
for(pii v : adj[u])
if(v.F != p)
{
h[v.F] = h[u] + v.S;
dfs(v.F, u);
}
Stack[pos] = saveLine;
stackSize = saveSize;
}
void solve()
{
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
}
for(int i = 2; i <= n; i++)
cin >> s[i] >> v[i];
dfs(1, 0);
for(int i = 2; i <= n; i++)
cout << f[i] << " ";
}
AutoAC
{
// clock_t START, FINISH;
// START = clock();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen (HUNGIT".inp", "r", stdin);
// freopen (HUNGIT".out", "w", stdout);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
// FINISH = clock();
// cout << fixed << setprecision(4);
// cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
19 ms |
39376 KB |
Memory limit exceeded |
2 |
Runtime error |
19 ms |
39920 KB |
Memory limit exceeded |
3 |
Runtime error |
44 ms |
47388 KB |
Memory limit exceeded |
4 |
Runtime error |
68 ms |
50696 KB |
Memory limit exceeded |
5 |
Runtime error |
90 ms |
54288 KB |
Memory limit exceeded |
6 |
Runtime error |
88 ms |
57616 KB |
Memory limit exceeded |
7 |
Runtime error |
55 ms |
48388 KB |
Memory limit exceeded |
8 |
Runtime error |
88 ms |
52596 KB |
Memory limit exceeded |
9 |
Runtime error |
95 ms |
54444 KB |
Memory limit exceeded |
10 |
Runtime error |
90 ms |
53256 KB |
Memory limit exceeded |