| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 566651 | 2022-05-22T14:13:32 Z | mars4 | Harbingers (CEOI09_harbingers) | C++17 | 112 ms | 26728 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define ll int64_t
#define ld long double
#define nl cout<<"\n"
#define i128 __int128_t
#define all(v) v.begin(),v.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define forn(i,a,b) for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b) for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1'000'000'007
#define mod2 998'244'353
#define inf 1'000'000'000'000'007
#define pi 3.14159265358979323846
template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;
template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p) {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s) {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class T> ostream& operator<<(ostream& out,ordered_set<T> &s) {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m) {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}
void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail>
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
//---------------------------------mars4---------------------------------
struct Line
{
ll m;
ll c;
Line(ll m,ll c):m(m),c(c) {}
ll eval(ll x)
{
return m*x+c;
}
};
class CHT
{
const ll logN=20;
ld intersectX(Line a,Line b)
{
return (ld)(a.c-b.c)/(b.m-a.m);
}
public:
vector<Line> cv_hull;
vector<ll> ind;
ll sz;
void init(ll n)
{
cv_hull=vector<Line>(n,Line(0,0));
ind=vector<ll>(n);
iota(all(ind),0);
}
ll get_pos(ll m,ll c)
{
Line line(m,c);
int stk_max=sz;
// check if hull is trivial or if line belongs at the end
if (stk_max < 2 ||
intersectX(line, cv_hull[stk_max - 1]) >= intersectX(cv_hull[stk_max - 1], cv_hull[stk_max - 2])) {
return stk_max;
}
// begin at l = 1 because we need to check intersection between k and k - 1
int l = 1, r = stk_max - 1;
while (l < r) {
int m = (l + r) / 2;
if (intersectX(line, cv_hull[m]) < intersectX(cv_hull[m], cv_hull[m - 1])) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
ll query(ll x)
{
ll cur=*lower_bound(ind.begin(),ind.begin()+sz-1,x,[&](ll i,ll x){
return intersectX(cv_hull[i],cv_hull[i+1])<x;
});
return cv_hull[cur].eval(x);
}
};
CHT cht;
vector<vector<pair<ll,ll>>> v;
vector<pair<ll,ll>> a;
vector<Line> g;
vector<ll> sz;
vector<ll> ans;
void dfs(ll cur,ll prev,ll dist)
{
if(cur)
{
ans[cur]=cht.query(a[cur].ss)+a[cur].ss*dist+a[cur].ff;
ll pos=cht.get_pos(-dist,ans[cur]);
g[cur]=cht.cv_hull[pos];
sz[cur]=cht.sz;
cht.cv_hull[pos]=Line(-dist,ans[cur]);
cht.sz=pos+1;
}
for(auto [i,w]:v[cur])
{
if(i!=prev)
{
dfs(i,cur,dist+w);
}
}
if(cur)
{
cht.cv_hull[cht.sz-1]=g[cur];
cht.sz=sz[cur];
}
}
int main()
{
fastio();
ll z,n,m,t,k,i,j,l,d,h,r;
cin>>n;
v=vector<vector<pair<ll,ll>>>(n);
a=vector<pair<ll,ll>>(n);
g=vector<Line>(n,Line(0,0));
sz=vector<ll>(n);
ans=vector<ll>(n);
cht.init(n);
forn(i,0,n-1)
{
cin>>l>>r>>d;
l--,r--;
v[l].push_back({r,d});
v[r].push_back({l,d});
}
forn(i,1,n)
{
cin>>a[i].ff>>a[i].ss;
}
cht.cv_hull.push_back({0,0});
cht.sz=1;
dfs(0,-1,0);
forn(i,1,n)
{
cout<<ans[i]<<" ";
}
nl;
cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 2 ms | 980 KB | Output is correct |
| 3 | Correct | 44 ms | 11152 KB | Output is correct |
| 4 | Correct | 56 ms | 16424 KB | Output is correct |
| 5 | Correct | 71 ms | 21576 KB | Output is correct |
| 6 | Correct | 112 ms | 26728 KB | Output is correct |
| 7 | Correct | 56 ms | 13860 KB | Output is correct |
| 8 | Correct | 111 ms | 20588 KB | Output is correct |
| 9 | Correct | 105 ms | 22436 KB | Output is correct |
| 10 | Correct | 98 ms | 21144 KB | Output is correct |