Submission #1168916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168916		PieArmy	Harbingers (CEOI09_harbingers)	C++20	0 / 100	96 ms	28484 KiB

harbingers

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

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

int find_par(int pos,int x){
	for(int i=0;i<17;i++){
		if((1<<i)&x){
			pos=par[pos][i];
		}
	}
	return pos;
}

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

	int las=find_par(pos,dep[pos]);
	while(dep[pos]>1){
		int cur=find_par(pos,dep[pos]-1);
		if(ans[las]-path[las]*v[pos]>=ans[cur]-path[cur]*v[pos]){
			las=cur;
			dep[pos]--;
			continue;
		}
		break;
	}
	ans[pos]=ans[las]+(path[pos]-path[las])*v[pos]+s[pos];

	int loc=pos;
	for(int i=17-1;i>=0;i--){
		if(dep[pos]-1<(1<<i))continue;
		int a=par[loc][i],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]-=(1<<i);
			loc=a;
		}
	}
	par[pos][0]=par[loc][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>>s[i]>>v[i];
	}
	dfs(1,1);
	for(int i=2;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}

• Subtask 1: 0 / 100