#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include"bits/stdc++.h"
using namespace std;
#define nl '\n'
#define sp ' '
#define dbg(i) cerr<<#i<<sp<<i<<endl
#define dbgs(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
using ll = long long;
// dont use below with atcoder header or tight constrain
// #define int ll
using pii = pair<int,int>;
int cur_tc;
std::mt19937_64 gen(time(NULL));
ll randint(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
/*Solution
https://acmicpc.net/problem/3319
1. 문제부터 정확히 읽는다.
2. 사고 전환을 빠르게 한다.
3. 한줄 한줄 정신 차리고 작성한다.
*/
constexpr int N = 1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7, LOOP = 3e5;
constexpr ll linf = (ll)4e18 + 7;
/*
rollback Line container for dynamic CHT that can be Rollbacked. (Persistent)
y = kx + m
qry: gives minimum value for given x, Lower hull
find bool operator< (const Line& o) to change minimum / maximum properties.
for minimum: k > o.k, x->m < y->m
for maximum: k < o.k, x->m > y->m
for doubles, change all (ll -> double), (inf -> 1/.0), (div(a,b) = a/b)
reference: https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
*/
struct Line{
mutable ll k, m, p;
bool operator<(const Line& o) const{return k!=o.k?k>o.k:m<o.m;} // chg here
bool operator<(ll x) const {return p < x;}
};
struct LineContainer : multiset<Line, less<>> {
static const ll inf = LLONG_MAX;
ll div(ll a, ll b){ // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool apply(iterator x, iterator y){
if(y == end()){
x->p = inf;
return false;
}
if(x->k == y->k) x->p = (*x<*y?inf:-inf);
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
vector<int> info; vector<Line> S;
bool add(ll k, ll m){
auto z = insert({k, m, -inf}), y = z++, x = y;
auto it = x; vector<Line> v;
while(apply(y, z)) v.push_back(*z), z = erase(z);
if(x != begin() && apply(--x, y)){
apply(x, y = erase(y));
assert(v.size() == 0); info.push_back(0);
return false;
}
reverse(v.begin(), v.end());
while((y=x) != begin() && (--x)->p >= y->p) v.push_back(*y), apply(x, erase(y));
assert(it != end()); v.push_back(*it);
S.insert(S.end(), v.begin(), v.end()); info.push_back(v.size());
return true;
}
void print_it(iterator it){dbgs("%dth %lld %lld %lld\n",(int)distance(begin(),it), it->k, it->m, it->p);}
void print(){
dbg(size());
for(auto it = begin(); it != end(); it++)
print_it(it);
}
void rollback(){
// print();
assert(!info.empty());
auto c = info.back(); info.pop_back();
if(c == 0) return;
assert(c <= S.size());
auto l = S.back(); S.pop_back(); --c;
auto it = lower_bound(l);
assert(it != end() && it->k == l.k && it->m == l.m);
it = erase(it);
if(c==0){
if(it != begin()) apply(prev(it), it);
return;
}
if(it != begin()) --it;
auto y = it;
for(int i=0;i<c;i++) y = insert(y, S.back()), S.pop_back();
if(it == next(y)) it = begin();
for(auto x = y++; ;--x, --y){// note that x's initial iterator is valid
apply(x, y);
if(x == it) break;
}
}
ll qry(ll x){
assert(!empty());
auto l = lower_bound(x); assert(l != end());
return l->k * x + l->m;
}
};
LineContainer lc;
vector<pii> g[N];
int par[N], S[N], V[N];
ll dep[N], dp[N];
void dfs(int x){
if(x != 1) dp[x] = S[x] + dep[x] * V[x] + lc.qry(V[x]);
lc.add(-dep[x], dp[x]);
for(auto [nx, d]:g[x]) if(nx != par[x]){
dep[nx] = dep[x] + d; par[nx] = x;
dfs(nx);
}
lc.rollback();
}
void solve(){
int n; cin>>n;
for(int i=0;i<n-1;i++){
int a, b, d; cin>>a>>b>>d;
g[a].push_back(pii(b,d)); g[b].push_back(pii(a,d));
}
for(int i=2;i<=n;i++) cin>>S[i]>>V[i];
lc.S.reserve(n); lc.info.reserve(n);
dfs(1);
for(int i=2;i<=n;i++) cout<<dp[i]<<sp;
cout<<nl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
// cout<<fixed<<setprecision(15);
int tc = 1;
// cin >> tc;
for(cur_tc=1;cur_tc<=tc;++cur_tc) solve();
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from harbingers.cpp:4:
harbingers.cpp: In member function 'void LineContainer::rollback()':
harbingers.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | assert(c <= S.size());
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5976 KB |
Output is correct |
| 3 |
Correct |
38 ms |
18508 KB |
Output is correct |
| 4 |
Correct |
57 ms |
24528 KB |
Output is correct |
| 5 |
Correct |
71 ms |
30180 KB |
Output is correct |
| 6 |
Runtime error |
94 ms |
35624 KB |
Memory limit exceeded |
| 7 |
Correct |
51 ms |
16720 KB |
Output is correct |
| 8 |
Execution timed out |
1042 ms |
24316 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1063 ms |
17040 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1034 ms |
27212 KB |
Time limit exceeded |
