Submission #482321

#	Time	Username	Problem	Language	Result	Execution time	Memory
482321		CSQ31	Harbingers (CEOI09_harbingers)	C++17	100 / 100	120 ms	19780 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 1e5;
int n;
ll dp[MAXN],t[MAXN],s[MAXN];
vector<pii>adj[MAXN];
struct line{
	ll m,c;
	line(ll _m,ll _c):m(_m),c(_c){}
	line(){}
	ll eval(ll x){return m*x+c;}
}hull[MAXN];

int szz = 0;
ll Div(ll a,ll b){return a / b + ((a^b) < 0 && (a%b));}
void dfs(int v,int u,int d){
	//cout<<v<<" "<<szz<<'\n';
	if(v){
		int l = -1,r = szz-1;
		while(r-l>1){
			int mid = (l+r)/2;
			if(hull[mid].eval(s[v]) >= hull[mid+1].eval(s[v]))l=mid;
			else r = mid;
			//r is first value that has mid<mid+1
		}
		dp[v] = d*1LL*s[v] +  hull[r].eval(s[v]) + t[v];
	}
	line x = line(-d,dp[v]);
	int old_szz = szz;
	int pos = 0;
	line prev;
	if(szz<2)pos = szz;
	else{
		int l =1,r=szz-1;
		while(r>=l){
			int mid = (l+r)/2;
			line f = hull[mid-1];
			line g = hull[mid];
			if(Div(f.c - g.c,g.m - f.m) < Div(g.c - x.c,x.m-g.m))l = mid+1;
			else r=mid-1;
		}
		pos = l;
	}
	szz = pos+1;
	if(pos != old_szz+1)prev = hull[pos];
	hull[pos] = x;
	
	
	for(pii x:adj[v]){
		if(x.fi==u)continue;
		dfs(x.fi,v,d+x.se);
	}
	if(pos != old_szz+1)hull[pos] = prev;
	szz = old_szz;
	
}
int main()
{
  owo
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--;
		v--;
		adj[v].pb({u,w});
		adj[u].pb({v,w});
	}
	for(int i=1;i<n;i++)cin>>t[i]>>s[i];
	dfs(0,-1,0);
	for(int i=1;i<n;i++)cout<<dp[i]<<" ";
	
}

• Subtask 1: 100 / 100