Submission #957568

#	Time	Username	Problem	Language	Result	Execution time	Memory
957568		noobcodur	Harbingers (CEOI09_harbingers)	C++14	100 / 100	96 ms	31828 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,j) for(int i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define pb push_back
#define s second
#define all(x) x.begin(),x.end()

const int MOD = 1e9 + 7; const int INF = 1e17 + 1; const int maxN = 2e5 + 1;

void setIO(string name = ""){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

struct Line{
	int m,c;

	int value(int x){
		return m*x + c;
	}

	double intersect(Line D){
		return ((c - D.c)/(D.m - m));
	}
};

Line L[maxN]; int V[maxN],S[maxN],dp[maxN],curr_sz = 0;

int min_val(int x){
	int lo = 0; int hi = curr_sz-1;

	while(lo < hi){
		int mid = (lo+hi)/2;

		if(L[mid].intersect(L[mid+1]) < x){
			lo = mid+1;
		}

		else{
			hi = mid;
		}
	} 

	return L[lo].value(x);
}

int pos(Line D){
	if(curr_sz <= 1 || D.intersect(L[curr_sz-1]) > L[curr_sz-1].intersect(L[curr_sz-2])){
		return curr_sz;
	}

	int lo = 1; int hi = curr_sz-1;

	while(lo < hi){
		int mid = (lo+hi)/2;

		if(D.intersect(L[mid]) < L[mid].intersect(L[mid-1])){
			hi = mid;
		}

		else{
			lo = mid+1;
		}
	}

	return lo;
}

vpii graph[maxN];

void dfs(int src, int prev, int d){
	for(auto [ch,dist] : graph[src]){
		if(ch == prev) continue;
		dp[ch] = min_val(V[ch]) + V[ch]*(d+dist) + S[ch];

		Line D = {-d-dist,dp[ch]};
		int curr = curr_sz;
		int curr_pos = curr_sz = pos(D); Line pre = L[curr_pos];
		L[curr_pos] = D; curr_sz++;


		dfs(ch,src,d+dist);

		//reset the changes

		L[curr_pos] = pre; curr_sz = curr;
	}
}

signed main(){
	setIO();
	int n; cin >> n;

	forn(i,n-1){
		int a,b,c; cin >> a >> b >> c;
		graph[a].pb({b,c}); graph[b].pb({a,c});
	}

	forrange(i,2,n+1){
		cin >> S[i] >> V[i];
	}

	L[0] = {0,0}; curr_sz++;
	dfs(1,-1,0);

	forrange(i,2,n+1){
		cout << dp[i] << " ";
	}
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:84:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |  for(auto [ch,dist] : graph[src]){
      |           ^
harbingers.cpp: In function 'void setIO(std::string)':
harbingers.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:23:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100