Submission #971981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971981	2024-04-29T16:12:27 Z	de_sousa	Harbingers (CEOI09_harbingers)	C++17	90 / 100	105 ms	24460 KB

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]};
	       return A[0]*B[1]<A[1]*B[0];
	  };

     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 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]};
	       }
	       
	       {
		    int L=0;
		    int R=Ssize-1;
		    while(L<R){
			 int mid=L+(R-L)/2;
			 if(cross(S[mid],S[mid+1],newVal))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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	2 ms	860 KB	Output is correct
3	Incorrect	31 ms	10120 KB	Output isn't correct
4	Correct	48 ms	15184 KB	Output is correct
5	Correct	55 ms	19796 KB	Output is correct
6	Correct	81 ms	24460 KB	Output is correct
7	Correct	39 ms	12260 KB	Output is correct
8	Correct	78 ms	18380 KB	Output is correct
9	Correct	105 ms	20060 KB	Output is correct
10	Correct	70 ms	18888 KB	Output is correct