Submission #1169085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169085		PieArmy	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	31304 KiB

harbingers

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int n;
vector<pair<int,ll>>komsu[100023];
ll v[100023];
ll opt[100023];
int par[100023][17],dep[100023];
ll path[100023],ans[100023];

void dfs(int pos,int root){
	for(int i=1;i<17;i++){
		par[pos][i]=par[par[pos][i-1]][i-1];
	}

	int loc=pos;
	for(int i=17-1;i>=0;i--){
		if(dep[loc]-1<(1<<i))continue;
		if(opt[par[loc][i]]>v[pos]){
			loc=par[loc][i];
		}
	}
	loc=par[loc][0];
	ans[pos]+=ans[loc]+(path[pos]-path[loc])*v[pos];

	while(dep[pos]>1){
		int a=par[pos][0],b=par[a][0];
		if(__int128_t(ans[pos]-ans[b])*__int128_t(path[a]-path[b])<=__int128_t(ans[a]-ans[b])*__int128_t(path[pos]-path[b])){
			dep[pos]--;
			par[pos][0]=b;
			continue;
		}
		break;
	}
	opt[pos]=ceil(double(ans[pos]-ans[par[pos][0]])/double(path[pos]-path[par[pos][0]]));

	for(int i=1;i<17;i++){
		par[pos][i]=par[par[pos][i-1]][i-1];
	}

	for(auto x:komsu[pos]){
		if(x.first==root)continue;
		path[x.first]=path[pos]+x.second;
		dep[x.first]=dep[pos]+1;
		par[x.first][0]=pos;
		dfs(x.first,pos);
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;cin>>x>>y>>z;
		komsu[x].push_back({y,z});
		komsu[y].push_back({x,z});
	}
	for(int i=2;i<=n;i++){
		cin>>ans[i]>>v[i];
	}
	dfs(1,1);
	for(int i=2;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}

• Subtask 1: 70 / 100