Submission #972043

#	Time	Username	Problem	Language	Result	Execution time	Memory
972043		de_sousa	Harbingers (CEOI09_harbingers)	C++17	100 / 100	91 ms	24440 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++){
	  long long 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)->long long
	  {
	       return x[0]*y+x[1];
	  };

     auto cross=[&](array<long long,2>&x,array<long long,2>&y,array<long long,2>&z)->long long
	  {
	       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]};
	       __int128 L=A[0];
	       L*=B[1];
	       __int128 R=A[1];
	       R*=B[0];
	       return L>=R;
	  };

     vector<long long> depth(n);
     
     vector<array<long long,2>> S(n,{0,0});
     int Ssize=1;
     
     vector<long long> sol(n);
     auto dfs=[&](auto&&dfs,int x,int p)->void
	  {
	       int oldSsize=Ssize;
	       
	       array<long long,2> newVal;
	       {
		    // int Siter=0;
		    // while(Siter+1<Ssize && eval(S[Siter],a[x][1])>eval(S[Siter+1],a[x][1]))Siter++;
		    // sol[x]=depth[x]*a[x][1] + eval(S[Siter],a[x][1]) + a[x][0];
		    
		    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;
		    }
		    
		    sol[x]=depth[x]*a[x][1] + eval(S[L],a[x][1]) + a[x][0];
		    
		    newVal={-depth[x],sol[x]};
	       }
	       
	       {
		    // while(Ssize>=2 && cross(S[Ssize-2],S[Ssize-1],newVal))Ssize--;
		    // ^- gives TLE but correct
		    

		    // we're gonna ask the question "can we pop?" everywhere we can, i.e.: [2,Ssize] ([2,Ssize+1))
		    // Ssize will be the last that answers no
		    int L=2;
		    int R=Ssize+1;
		    Ssize=1;

		    while(L<R){
			 int mid=L+(R-L)/2;
			 // if we put the value at mid, can it be popped?
			 if(cross(S[mid-2],S[mid-1],newVal)){ // yes
			      // Ssize must be below mid
			      R=mid;
			 }
			 else{ // no
			      // Ssize can be mid or above, since L is growing, let's put it right now
			      Ssize=mid;
			      L=mid+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: 100 / 100