#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, d[N], s[N], speed[N];
long long f[N];
vector <ii> ke[N];
struct CHT
{
struct line
{
long long A, B;
line() {};
line(long long A, long long B) : A(A), B(B) {};
double cut(line l)
{
return 1.0 * (l.B - B) / (A - l.A);
}
long long get(long long qx)
{
return A * qx + B;
}
};
vector <line> vt; stack <line> VT[N];
vector <double> x; stack <double> X[N];
vector <int> lst; stack <int> LST[N];
bool ok = 0;
void add(line l, int u)
{
if(!ok)
{
ok = 1;
vt.push_back(l);
x.push_back(-1e18);
lst.push_back(u);
return ;
}
while (vt.size() > 1 && l.cut(vt[vt.size() - 2]) <= x.back())
{
VT[u].push(vt.back()); vt.pop_back();
X[u].push(x.back()); x.pop_back();
LST[u].push(lst.back()); lst.pop_back();
}
if(!vt.empty()) x.push_back(l.cut(vt.back()));
vt.push_back(l);
lst.push_back(u);
// cout << u << "**\n";
// for(int o : lst) cout << o << " ";
// cout << "\n\n";
}
long long query(long long qx)
{
// if(qx == 6)
// {
// for(double o : lst) cout << o << " ";
// cout << "\n";
// }
int id = upper_bound(x.begin(), x.end(), qx) - x.begin() - 1;
return vt[id].get(qx);
}
void del(int u)
{
// cout << u << "^^\n";
if(lst.back() == u)
{
vt.pop_back();
x.pop_back();
lst.pop_back();
while (!LST[u].empty())
{
lst.push_back(LST[u].top()); LST[u].pop();
x.push_back(X[u].top()); X[u].pop();
vt.push_back(VT[u].top()); VT[u].pop();
}
}
// for(double o : lst) cout << o << " ";
// cout << "\n\n";
}
} cht;
void dfs(int u, int pre)
{
for(auto [v, w] : ke[u]) if(v != pre)
{
d[v] = d[u] + w;
f[v] = s[v] + d[v] * speed[v] - cht.query(speed[v]);
cht.add(CHT :: line(d[v], -f[v]), v);
dfs(v, u);
cht.del(v);
}
}
main ()
{
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r"))
{
freopen("task.inp", "r", stdin);
freopen("wa.out", "w", stdout);
}
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v, w; cin >> u >> v >> w;
ke[u].push_back({v, w});
ke[v].push_back({u, w});
}
for(int i = 2; i <= n; i++) cin >> s[i] >> speed[i];
cht.add(CHT :: line(0, 0), 1);
dfs(1, 0);
for(int i = 2; i <= n; i++) cout << f[i] << " ";
}
Compilation message
harbingers.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
102 | main ()
| ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen("task.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen("wa.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
33 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
35 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
33 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
40 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
