Submission #1168951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168951		PieArmy	Harbingers (CEOI09_harbingers)	C++20	0 / 100	1097 ms	27068 KiB

harbingers

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

struct Seg{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n<<1,1e9+1);
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=r;
			return;
		}
		int mid=(left+right)/2;
		if(l>mid)up(node+(mid-left+1)*2,mid+1,right);
		else up(node+1,left,mid);
		tree[node]=min(tree[node+1],tree[node+(mid-left+1)*2]);
	}
	void update(int tar,int x){
		l=tar;r=x;
		up();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(tree[node]>r)return -1;
		if(left==right){
			return left;
		}
		int mid=(left+right)/2;
		if(l>mid){
			int res=qu(node+(mid-left+1)*2,mid+1,right);
			if(res!=-1)return res;
		}
		return qu(node+1,left,mid);
	}
	int query(int tar,int x){
		l=tar;r=x;
		return qu();
	}
};

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

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){
	if(pos!=1){
		par[pos][0]=seg.query(lis.size()-1,v[pos]);
		dep[pos]=dep[par[pos][0]]+1;
	}
	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];
	seg.update(lis.size(),v[pos]);
	lis.push_back(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;
		}
	}

	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;
		dfs(x.first,pos);
	}
	lis.pop_back();
	seg.update(lis.size(),1e9+1);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	seg.init(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