Submission #131595

#	Time	Username	Problem	Language	Result	Execution time	Memory
131595		onjo0127	Harbingers (CEOI09_harbingers)	C++11	100 / 100	269 ms	27024 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

long long D[100009];

struct line {
	int A, B;
	long long get(int x) { return 1LL*A*x + D[B]; }
};

struct node {
	int lc, rc;
	line l;
};

const int iNF = 1e9;
const long long INF = 5LL * 1e18;
node EMP = {-1, -1, {0, 100001}};

vector<int> VS;
node T[900009]; int to, rs, re, rm, m;

void add(node pi, node &ni, int s, int e, line L) {
	// printf("add: (%d, %d)\n", L.A, L.B);
	ni = pi;
	m = s+e >> 1;
	rs = VS[s-1], re = VS[e-1], rm = VS[m-1];
	if(L.get(rs) >= ni.l.get(rs) && L.get(re) >= ni.l.get(re)) return;
	if(L.get(rs) <= ni.l.get(rs) && L.get(re) <= ni.l.get(re)) {ni.l = L; return;}
	if(L.get(rs) > ni.l.get(rs)) swap(L, ni.l);
	if(L.get(rm) < ni.l.get(rm)) {
		swap(L, ni.l);
		ni.rc = to; T[to++] = EMP;
		if(pi.rc == -1) add(EMP, T[ni.rc], m, e, L);
		else add(T[pi.rc], T[ni.rc], m, e, L);
	}
	else {
		ni.lc = to; T[to++] = EMP;
		if(pi.lc == -1) add(EMP, T[ni.lc], s, m, L);
		else add(T[pi.lc], T[ni.lc], s, m, L);
	}
}
long long get(node id, int s, int e, int x) {
	// printf("get: (%lld, %lld)\n", id.l.A, id.l.B);
	if(x < s || e < x) return INF;
	m = s+e >> 1;
	long long ret = id.l.get(VS[x-1]);
	if(id.lc != -1) ret = min(ret, get(T[id.lc], s, m, x));
	if(id.rc != -1) ret = min(ret, get(T[id.rc], m, e, x));
	return ret;
}

int S[100009], V[100009], K;
vector<pii> adj[100009];

int getx(int x) {
	return lower_bound(VS.begin(), VS.end(), x) - VS.begin() + 1;
}

void dfs(int x, int p, int de) {
	if(x != 1) D[x] = get(T[S[p]], 1, K, getx(V[x])) + 1LL*de*V[x] + S[x];
	S[x] = to; T[to++] = EMP;
	add(T[S[p]], T[S[x]], 1, K, {-de, x});
	for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, de + it.second);
	to = S[x];
}

int main() {
	D[100001] = INF;
	int N; scanf("%d",&N);
	for(int i=0; i<N-1; 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(int i=2; i<=N; i++) {
		scanf("%d%d",&S[i],&V[i]);
		VS.push_back(V[i]);
	}
	sort(VS.begin(), VS.end()); VS.resize(unique(VS.begin(), VS.end()) - VS.begin());
	K = VS.size();
	T[to++] = EMP;
	dfs(1, 0, 0);
	for(int i=2; i<=N; i++) printf("%lld ", D[i]);
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void add(node, node&, int, int, line)':
harbingers.cpp:27:7: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  m = s+e >> 1;
      ~^~
harbingers.cpp: In function 'long long int get(node, int, int, int)':
harbingers.cpp:47:7: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  m = s+e >> 1;
      ~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:71: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:73:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d%d%d",&u,&v,&w);
                ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:78: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