Submission #211882

#	Time	Username	Problem	Language	Result	Execution time	Memory
211882		arnold518	Harbingers (CEOI09_harbingers)	C++14	100 / 100	192 ms	25708 KiB

harbingers

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N;
vector<pii> adj[MAXN+10];
ll L[MAXN+10], S[MAXN+10], V[MAXN+10], dp[MAXN+10];

struct Line { ll a, b; };
long double cross(const Line &p, const Line &q) { return ((long double)(q.b-p.b))/(p.a-q.a); }

struct CHT
{
	vector<Line> S; int sz=0; 
	vector<int> S1; vector<Line> S2;
	void update(Line p)
	{
		S1.push_back(sz);
		if(sz!=0 && S[sz-1].a==p.a)
		{
			if(S[sz-1].b<=p.b)
			{
				S2.push_back(S[sz-1]);
				return;
			}
			else sz--;
		}

		int lo=0, hi=sz;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(mid==0 || cross(S[mid], S[mid-1])<cross(S[mid], p)) lo=mid;
			else hi=mid;
		}
		if(hi==S.size()) S.push_back({-1, -1});
		sz=hi;
		S2.push_back(S[sz]);
		S[sz++]=p;
	}

	ll query(ll x)
	{
	    int lo=0, hi=sz;
	    while(lo+1<hi)
	    {
	        int mid=lo+hi>>1;
	        long double now;

	        if(mid==0) now=-1e9;
	        else now=cross(S[mid], S[mid-1]);

	        if(now<=x) lo=mid;
	        else hi=mid;
	    }
	    return S[lo].a*x+S[lo].b;
	}

	void restore()
	{
		S[sz-1]=S2.back(); S2.pop_back();
		sz=S1.back(); S1.pop_back();
	}
};
CHT cht;

void dfs1(int now, int bef, ll dep)
{
	L[now]=dep;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs1(nxt.first, now, dep+nxt.second);
	}
}

void dfs2(int now, int bef)
{
	if(now!=1) dp[now]=cht.query(V[now])+S[now]+L[now]*V[now];
	cht.update({-L[now], dp[now]});

	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs2(nxt.first, now);
	}

	cht.restore();
}

int main()
{
	int i, j;

	scanf("%d", &N);
	for(i=1; i<N; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for(i=2; i<=N; i++) scanf("%lld%lld", &S[i], &V[i]);

	dfs1(1, 1, 0);
	dfs2(1, 1);

	for(i=2; i<=N; i++) printf("%lld ", dp[i]);
}

Compilation message (stderr)

harbingers.cpp: In member function 'void CHT::update(Line)':
harbingers.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
harbingers.cpp:42:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(hi==S.size()) S.push_back({-1, -1});
      ~~^~~~~~~~~~
harbingers.cpp: In member function 'll CHT::query(ll)':
harbingers.cpp:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
          int mid=lo+hi>>1;
                  ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:99:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
harbingers.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
harbingers.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:109:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=2; i<=N; i++) scanf("%lld%lld", &S[i], &V[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100