Submission #1265835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265835		nanaseyuzuki	Harbingers (CEOI09_harbingers)	C++20	100 / 100	65 ms	19880 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
typedef pair<int , int> pii;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n , V[maxn] , S[maxn] , dp[maxn] , d[maxn] , len = 0;
pii cvh[maxn];
vector<pii> adj[maxn];
struct line
{
	pii last_line;
	int pos , last_len;
};
vector<line> cur;
int cal(int m , int x , int b)
{
	return m * x + b;
}
int get(int x)
{
	int l = 0 , r = len - 1;
	int minn = cal(cvh[0].fi , x , cvh[0].se);
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(cal(cvh[mid].fi , x , cvh[mid].se) < cal(cvh[mid + 1].fi , x , cvh[mid + 1].se))
		{
			r = mid;
			minn = min(minn , cal(cvh[mid].fi , x , cvh[mid].se));
		}
		else
		{
			l = mid + 1;
			minn = min(minn , cal(cvh[mid + 1].fi , x , cvh[mid + 1].se));
		}
	}
	return minn;
}
bool check(pii l1 , pii l2 , pii l3)
{
	return (double)(l3.se - l1.se) / (double)(l1.fi - l3.fi) <= (double)(l2.se - l1.se) / (double)(l1.fi - l2.fi);
}
void add(int m , int b)
{
	int l = 1 , r = len - 1 , p = len;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(cvh[mid - 1] , cvh[mid] , {m , b}))
		{
			p = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cur.pb({cvh[p] , p , len});
	len = p + 1;
	cvh[p] = {m , b};
}
void remove()
{
	line gan = cur.back();
	cur.pop_back();
	cvh[gan.pos] = gan.last_line;
	len = gan.last_len;
}
void dfs(int u , int par)
{
	if(u != 1) dp[u] = get(V[u]) + d[u] * V[u] + S[u];
	add(-d[u] , dp[u]);
	for(auto v : adj[u])
	{
		if(v.fi != par)
		{
			d[v.fi] = d[u] + v.se;
			dfs(v.fi , u);
		}
	}
	remove();
}
main()
{
    faster
    cin >> n;
    for(int i = 1 ; i <= n - 1 ; ++i)
	{
    	int u , v , d;
    	cin >> u >> v >> d;
    	adj[u].pb({v , d});
    	adj[v].pb({u , d});
	}
	for(int i = 2 ; i <= n ; ++i) cin >> S[i] >> V[i];
	dfs(1 , -1);
	for(int i = 2 ; i <= n ; ++i) cout << dp[i] << " ";
}

Compilation message (stderr)

harbingers.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main()
      | ^~~~

• Subtask 1: 100 / 100