#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<int,int>
#define pb push_back
#define sz size
#define f first
#define s second
const int mxN = 1e5;
int start[mxN];
int speed[mxN];
vector<pii> adj[mxN];
ll dp[mxN];
ll dist[mxN];
ll comp(int a, int b){
if (dist[b] < dist[a]) swap(a,b);
return (ll) ceil((double) (dp[b] - dp[a]) / (double) (dist[b] - dist[a]));
}
deque<int> all;
void dfs(int node, int p){
dp[node] = 0;
int r = all.sz()-1;
int l = -1;
int curr;
while (r - l > 1){
curr = (r+l)/2;
// cout << comp(all[curr],all[curr+1]) << "-" << all[curr] << " " << all[curr+1] << '\n';
if (comp(all[curr],all[curr+1]) <= (ll) speed[node]){
l = curr;
} else {
r = curr;
}
}
/* cout << node << " " << r << ": ";
for (int i =0; i < all.sz(); i++){
cout << all[i] << " ";
}
cout << "\n";*/
if (l != r){
dp[node] = dp[r] + (dist[node] - dist[r]) * (ll) speed[node] + (ll) start[node];
}
stack<int> rem;
while (all.sz() > 1 && comp(all[all.sz()-1],all[all.sz()-2]) >= comp(all[all.sz()-1],node)){
// cout << comp(all[all.sz()-1],all[all.sz()-2]) << " " << comp(all[all.sz()-1],node) << "\n";
rem.push(all[all.sz()-1]);
all.pop_back();
}
all.push_back(node);
for (pii next : adj[node]){
if (next.f != p){
dist[next.f] = dist[node] + next.s;
dfs(next.f,node);
}
}
all.pop_back();
while (rem.sz()>0){
all.push_back(rem.top());
rem.pop();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int a,b,d;
for (int i =0; i < n-1; i++){
cin >> a >> b >> d;
a -= 1;
b -= 1;
adj[a].pb({b,d});
adj[b].pb({a,d});
}
start[0] = 0;
speed[0] = 0;
for (int i =1; i < n; i++) cin >> start[i] >> speed[i];
dist[0] = 0;
dfs(0,-1);
for (int i =1; i < n; i++){
cout << dp[i] << " ";
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 3 |
Runtime error |
52 ms |
37412 KB |
Memory limit exceeded |
| 4 |
Runtime error |
65 ms |
53496 KB |
Memory limit exceeded |
| 5 |
Runtime error |
78 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
91 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Incorrect |
58 ms |
27840 KB |
Output isn't correct |
| 8 |
Runtime error |
89 ms |
40400 KB |
Memory limit exceeded |
| 9 |
Runtime error |
130 ms |
54352 KB |
Memory limit exceeded |
| 10 |
Runtime error |
122 ms |
48076 KB |
Memory limit exceeded |
