제출 #971866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971866		de_sousa	Harbingers (CEOI09_harbingers)	C++17	90 / 100	128 ms	26984 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define all(x) begin(x),end(x)

template<class T>
using iset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void solve(){
     
     int n;
     cin>>n;
     vector<vector<array<long long,2>>> g(n);
     for(int i=1;i<n;i++){
	  int x,y,z;
	  cin>>x>>y>>z;
	  x--;
	  y--;
	  g[x].push_back({y,z});
	  g[y].push_back({x,z});
     }
     
     vector<array<long long,2>> a(n);
     for(int i=1;i<n;i++){
	  cin>>a[i][0]>>a[i][1];
     }

     auto eval=[&](array<long long,2>&x,long long y)
	  {
	       return x[0]*y+x[1];
	  };

     auto cross=[&](array<long long,2>&x,array<long long,2>&y,array<long long,2>&z)
	  {
	       array<long long,2> A{y[0]-x[0],y[1]-x[1]};
	       array<long long,2> B{z[0]-y[0],z[1]-y[1]};
	       return A[0]*B[1]-A[1]*B[0];
	  };

     vector<long long> depth(n);
     
     vector<array<long long,2>> S(n);
     int Ssize=1;
     S[0]={0,0};

     vector<long long> sol(n);
     auto dfs=[&](auto&&dfs,int x,int p)->void
	  {
	       int oldSsize=Ssize;
	       
	       array<long long,2> newVal;
	       {
		    int L=0;
		    int R=Ssize-1;
		    while(L<R){
			 int mid=L+(R-L)/2;
			 if(eval(S[mid],a[x][1])>=eval(S[mid+1],a[x][1]))L=mid+1;
			 else R=mid;
		    }
		    auto[A,B]=S[L];
		    
		    sol[x]=depth[x]*a[x][1] + a[x][0] + A*a[x][1] + B;
		    newVal={-depth[x],sol[x]};
	       }
	       
	       {
		    int L=0;
		    int R=Ssize-1;
		    while(L<R){
			 int mid=L+(R-L)/2;
			 if(cross(S[mid],S[mid+1],newVal)<=0)L=mid+1;
			 else R=mid;
		    }
		    Ssize=L+1;
	       }
	       
	       auto oldVal=S[Ssize];
	       S[Ssize]=newVal;
	       Ssize++;
	       
	       for(auto[y,z]:g[x]){
		    if(y==p)continue;
		    depth[y]=depth[x]+z;
		    dfs(dfs,y,x);
	       }

	       Ssize--;
	       S[Ssize]=oldVal;
	       Ssize=oldSsize;
	  };
     
     for(auto[x,y]:g[0]){
	  depth[x]=y;
	  dfs(dfs,x,0);
     }

     for(int i=1;i<n;i++){
	  cout<<sol[i]<<" \n"[i==n-1];
     }
}

int main(){
     ios::sync_with_stdio(false);
     cin.tie(NULL);
     
     int numberOfTests=1;
     //cin>>numberOfTests;
     while(numberOfTests--){
	  solve();
     }
}

• Subtask 1: 90 / 100