oj.uz

Submission #130760

# Submission time Handle Problem Language Result Execution time Memory
130760 2019-07-16T04:39:24 Z 이온조(#3169) Harbingers (CEOI09_harbingers) C++14
20 / 100
 9 ms 5244 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct line {
	long long A, B;
	long long get(int x) { return A*x + B; }
};

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

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

node T[200009]; int to;

struct pslihao {
	int root[100009];
	void add(node pi, node &ni, int s, int e, line L) {
		// printf("add: (%d, %d)\n", L.A, L.B);
		ni = pi;
		if(L.get(s) >= ni.l.get(s) && L.get(e) >= ni.l.get(e)) return;
		if(L.get(s) <= ni.l.get(s) && L.get(e) <= ni.l.get(e)) {ni.l = L; return;}
		int m = s+e >> 1;
		if(L.get(s) > ni.l.get(s)) swap(L, ni.l);
		if(L.get(m) < ni.l.get(m)) {
			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;
		int m = s+e >> 1;
		long long ret = id.l.get(x);
		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;
	}
	pslihao() {
		T[to++] = EMP;
	}
} CH;

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

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

int main() {
	int N; scanf("%d",&N);
	assert(N <= 2500);
	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]);
	dfs(1, 0, 0);
	for(int i=2; i<=N; i++) printf("%lld ", D[i]);
	return 0;
}

Compilation message

harbingers.cpp: In member function 'void pslihao::add(node, node&, int, int, line)':
harbingers.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
harbingers.cpp: In member function 'long long int pslihao::get(node, int, int, int)':
harbingers.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:68: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:71: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:75:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=2; i<=N; i++) scanf("%d%d",&S[i],&V[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 7 ms 3448 KB Output is correct
3 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 9 ms 5244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)