Submission #972029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972029	2024-04-29T18:21:40 Z	de_sousa	Harbingers (CEOI09_harbingers)	C++17	0 / 100	77 ms	24400 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]};
	       }
	       
	       {
		    // while(Ssize>=2 && cross(S[Ssize-2],S[Ssize-1],newVal)>=0)Ssize--;
		    // ^- gives TLE but correct


		    // the element can be inserted in the range [L,R)
		    // int this case, [1,Ssize+1).
		    // if it can be inserted at position Ssize, then L=mid+1 will make it one above the possible
		    // if we can insert at position X, then cross(X-2,X-1,newVal)<0 AND cross(X-1,X,newVal)>=0
		    
		    int L=2;
		    int R=Ssize+1;
		    while(L<R){
			 int mid=L+(R-L)/2;
			 if(cross(S[mid-2],S[mid-1],newVal)<0)L=mid+1;
			 else R=mid;
		    }
		    
		    Ssize=L;
	       }
	       
	       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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	Output isn't correct
2	Incorrect	2 ms	860 KB	Output isn't correct
3	Incorrect	27 ms	10200 KB	Output isn't correct
4	Incorrect	51 ms	15068 KB	Output isn't correct
5	Incorrect	57 ms	20048 KB	Output isn't correct
6	Incorrect	72 ms	24400 KB	Output isn't correct
7	Incorrect	39 ms	12368 KB	Output isn't correct
8	Incorrect	77 ms	18376 KB	Output isn't correct
9	Incorrect	68 ms	20168 KB	Output isn't correct
10	Incorrect	55 ms	18896 KB	Output isn't correct