#include <bits/stdc++.h>
using namespace std;
// clang-format off
#define fi first
#define se second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int32_t)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define left Kurumi_Tokisaki
#define right Kei_Karuizawa
#define next Mai_Sakurajima
#define div Yume_Irido
#define prev Chizuru_Mizuhara
#define cntbit(x) __builtin_popcountll(x)
#define MASK(x) ( 1ll << (x) )
#define Yes cout << "Yes"
#define YES cout << "YES"
#define No cout << "No"
#define NO cout << "NO"
#define AA cout << "Alice"
#define BB cout << "Bob"
/// TASK
/// -----------------------------
#ifdef LMQZZZ
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << " ]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[ in " <<__func__<< "() : line " <<__LINE__<< " ] : [ " << #x << " ] = [ "; _print(x); cerr << '\n';
#define TASK "C"
#else
#define deb(x...) 3326
#define TASK "HARBINGERS"
#endif
///------------------------------
void lmqzzz();
void init() {};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
/// =================================
constexpr bool MULTITEST = 0;
/// ================================
init();
int32_t TT = 1;
if ( MULTITEST ) cin >> TT;
for(int32_t TTT = 1; TTT <= TT; TTT ++) {
lmqzzz();
cout << '\n';
}
}
template <class T> inline T min(const T &a, const T &b, const T &c) { return min(a, min(b, c)); }
template <class T> inline T max(const T &a, const T &b, const T &c) { return max(a, max(b, c)); }
template <class T, class U> inline bool mini(T &a, const U &b) { if (a > b) { a = b; return 1; } return 0; }
template <class T, class U> inline bool maxi(T &a, const U &b) { if (a < b) { a = b; return 1; } return 0; }
constexpr int16_t dr[] = {0, 0, -1, 1};
constexpr int16_t dc[] = {1, -1, 0, 0};
constexpr int64_t MOD = 1e9 + 7;
constexpr int32_t MAXN = 1e5 + 10;
// clang-format on
int n;
int a[MAXN], b[MAXN], d[MAXN];
vector<pair<int, int>> adj[MAXN];
vector<int64_t> query_points;
class line_t {
public:
int64_t a, b;
line_t(int64_t a = 0, int64_t b = 0) : a(a), b(b) {}
int64_t operator()(const int64_t &x) const {
return a * x + b;
}
};
vector<pair<line_t *, line_t>> rollback;
class lichaotree_t {
public:
lichaotree_t *left, *right;
int l, m, r;
line_t line;
lichaotree_t(int l = 0, int r = sz(query_points) - 1) : line(0, 1e18) {
int m = l + r >> 1;
this->l = query_points[l];
this->r = query_points[r];
this->m = query_points[m];
if (l == r) return;
left = new lichaotree_t(l, m);
right = new lichaotree_t(m + 1, r);
}
void add(int64_t a, int64_t b) {
line_t new_line(a, b);
bool better_l = line(l) >= new_line(l);
bool better_r = line(r) >= new_line(r);
if (better_l && better_r) {
rollback.eb(&line, line);
line = new_line;
return;
} else if (better_l || better_r) {
left->add(a, b);
right->add(a, b);
}
}
int64_t getmin(const int &x) {
if (l == r) return line(x);
if (x <= m) return min(left->getmin(x), line(x));
return min(right->getmin(x), line(x));
}
} *tree;
int64_t f[MAXN];
void dfs(int u, int p) {
f[u] = u == 1 ? 0 : tree->getmin(a[u]) + b[u] + 1ll * d[u] * a[u];
tree->add(-d[u], f[u]);
for (pair<int, int> &e : adj[u]) {
int v = e.fi;
if (v == p) continue;
d[v] = d[u] + e.se;
int old_size = sz(rollback);
dfs(v, u);
while (sz(rollback) > old_size) {
*rollback.back().fi = rollback.back().se;
rollback.pop_back();
}
}
}
void lmqzzz() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, c;
cin >> u >> v >> c;
adj[u].eb(v, c);
adj[v].eb(u, c);
}
for (int i = 2; i <= n; i++) {
cin >> b[i] >> a[i];
query_points.eb(a[i]);
}
uniquev(query_points);
tree = new lichaotree_t();
dfs(1, 1);
for (int i = 2; i <= n; i++) cout << f[i] << ' ';
}
Compilation message
harbingers.cpp: In constructor 'lichaotree_t::lichaotree_t(int, int)':
harbingers.cpp:123:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int m = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:74:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen(TASK ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:75:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen(TASK ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3460 KB |
Output is correct |
| 3 |
Correct |
60 ms |
21532 KB |
Output is correct |
| 4 |
Correct |
81 ms |
27420 KB |
Output is correct |
| 5 |
Runtime error |
137 ms |
34528 KB |
Memory limit exceeded |
| 6 |
Correct |
126 ms |
24696 KB |
Output is correct |
| 7 |
Correct |
66 ms |
13832 KB |
Output is correct |
| 8 |
Correct |
139 ms |
32568 KB |
Output is correct |
| 9 |
Runtime error |
148 ms |
37832 KB |
Memory limit exceeded |
| 10 |
Runtime error |
143 ms |
33056 KB |
Memory limit exceeded |
