oj.uz

Submission #130730

# Submission time Handle Problem Language Result Execution time Memory
130730 2019-07-16T04:19:16 Z 이온조(#3169) Harbingers (CEOI09_harbingers) C++14
0 / 100
 98 ms 14196 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}};

struct pslihao {
	vector<node> T;
	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 = T.size(); T.push_back(EMP);
			add(T[pi.rc], T[ni.rc], m, e, L);
		}
		else {
			ni.lc = T.size(); T.push_back(EMP);
			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.push_back(EMP);
	}
} CH;

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

void dfs(int x, int p, int de) {
	// printf("x: %d, p: %d, de: %d\n", x, p ,de);
	if(x != 1) D[x] = CH.get(CH.T[CH.root[p]], 1, iNF, V[x]) + 1LL*de*V[x] + S[x];
	// printf("D[%d]: %lld\n", x, D[x]);
	// puts("getted");
	CH.root[x] = CH.T.size(); CH.T.push_back(EMP);
	CH.add(CH.T[CH.root[p]], CH.T[CH.root[x]], 1, iNF, {-de, D[x]});
	// puts("added");
	for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, de + it.second);
}

int main() {
	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]);
	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:27: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:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:69: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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 9 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 44 ms 8540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 62 ms 10128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 80 ms 11764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 97 ms 13176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 63 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 95 ms 13428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 98 ms 13836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 85 ms 14196 KB Execution killed with signal 11 (could be triggered by violating memory limits)