Submission #148112

#	Time	Username	Problem	Language	Result	Execution time	Memory
148112		WhipppedCream	Harbingers (CEOI09_harbingers)	C++17	100 / 100	614 ms	27896 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long L;
typedef vector< L > vL;
typedef vector< vL > vvL;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
const int inf = 1e9;
const L inf8 = 1e18;
const int maxn = 1e5 + 5;
vii adj[maxn];
int s[maxn], v[maxn];
int dp[25][maxn];
int Depth[maxn];
L res[maxn];
struct node
{
	L m, b;
	node(L x, L y)
	{
		m = x; b = y;
	}
};
node* root[maxn];
int getAnc(int lev, int u)
{
	for(int i = 20; i>= 0; i--)
	{
		if((1<<i)<= lev)
		{
			lev -= (1<<i);
			u = dp[i][u];
		}
	}
	return u;
}
double getInt(node *A, node *B)
{
	double m1 = A->m, b1 = A->b;
	double m2 = B->m, b2 = B->b;
	return (double) (b2-b1)/(m1-m2);
}
L eval(node *A, L x)
{
	return A->m*x + A->b;
}
L query(int to, L x, int dep)
{
	if(dep == 1)
	{
		return eval(root[to], x);
	}
	//printf("%d %lld %d\n", to, x, dep);
	if(dep>= 2)
	{
		int here = getAnc(dep-2, to);
		if((double) x<= getInt(root[1], root[here])) return eval(root[1], x);
	}
	int lo = 0, hi = dep-2;
	//printf("correct\n");
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		int x2 = getAnc(mid, to);
		int x1 = dp[0][x2];
		double Int = getInt(root[x1], root[x2]);
		//printf("trying %d\n", x1);
		//cout << Int << endl;
		if(Int<= (double) x) hi = mid;
		else lo = mid+1;
	}
	//printf("lo is %d\n", lo);
	//printf("getAnc is %d\n", getAnc(lo, to));
	return eval(root[getAnc(lo, to)], x);
}
bool bad(node *A, node *B, node *C)
{
	double m1 = A->m, b1 = A->b;
	double m2 = B->m, b2 = B->b;
	double m3 = C->m, b3 = C->b;
	double x1 = (double) (b3-b1)/(m1-m3);
	double x2 = (double) (b1-b2)/(m2-m1);
	return x1<= x2;
}
int add(int to, int adder)
{
	int d = Depth[to];
	int lo = 0, hi = d-1;
	if(d < 2) return to;
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		int x2 = getAnc(mid, to);
		int x1 = dp[0][x2];
		if(x1 == 0) hi = mid;
		else if(bad(root[x1], root[x2], root[adder])) lo = mid+1;
		else hi = mid;
	}
	return getAnc(lo, to);
}
void solve(int u, int p, L dist)
{
	//printf("%d\n", u);	
	res[u] = query(p, v[u], Depth[p]) + dist*v[u]+s[u];
	//printf("query with %d\n", v[u]);
	//printf("%lld\n",query(p, v[u], Depth[p])); 
	//printf("...\n");
	root[u] = new node(-dist, res[u]);
	//printf("insert! %lld %lld\n", -dist, res[u]);
	int k = add(p, u);
	//printf("k is %d\n", k);
	Depth[u] = Depth[k]+1;
	dp[0][u] = k;
	for(int i = 1; i<= 20; i++) dp[i][u] = dp[i-1][dp[i-1][u]];
	for(auto kk : adj[u])
	{
		int v = kk.X, w = kk.Y;
		if(v == p) continue;
		solve(v, u, dist+w);
	}
}
int main()
{
	int n; scanf("%d", &n);
	for(int i = 0; i< n-1; i++)
	{
		int a, b, w; scanf("%d %d %d", &a, &b, &w);
		adj[a].pb(ii(b, w)); adj[b].pb(ii(a, w));
	}
	for(int i = 2; i<= n; i++)
	{
		scanf("%d %d", s+i, v+i);
	}
	root[1] = new node(0, 0);
	Depth[1] = 1;
	for(auto kk : adj[1])
	{
		solve(kk.X, 1, kk.Y);
	}
	for(int i = 2; i<= n; i++) printf("%lld ", res[i]);
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
harbingers.cpp:134:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, w; scanf("%d %d %d", &a, &b, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", s+i, v+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100