제출 #971977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971977		de_sousa	Harbingers (CEOI09_harbingers)	C++17	20 / 100	1098 ms	12976 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];
     }

     vector<long long> sol(n);
     vector<int> father(n);
     vector<long long> depth(n);
     auto dfs=[&](auto&&dfs,int x)->void
	  {

	       sol[x]=depth[x]*a[x][1]+a[x][0];
	       {
		    int y=father[x];
		    while(y!=0){
			 sol[x]=min(sol[x], (depth[x]-depth[y])*a[x][1] + a[x][0] + sol[y] );
			 y=father[y];
		    }
	       }
	       
	       for(auto[y,z]:g[x]){
		    if(y==father[x])continue;
		    depth[y]=depth[x]+z;
		    father[y]=x;
		    dfs(dfs,y);
	       }
	  };
     for(auto[x,y]:g[0]){
	  father[x]=0;
	  depth[x]=y;
	  dfs(dfs,x);
     }

     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: 20 / 100