oj.uz

답안 #528184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528184 2022-02-19T16:07:51 Z sidon Harbingers (CEOI09_harbingers) C++17
20 / 100
 184 ms 65544 KB 
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 1e9, INF = 2e9;

struct Line {
	int m, c;
	Line(int M = 0, int C = INF) : m(M), c(C) {}
	int operator()(int x) {
		return m * x + c;
	}
};

struct LiChaoTree {
	Line v;
	LiChaoTree *L = NULL, *R = NULL;
	void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
		int m = (l + r) / 2;
		if(u(m) < v(m)) {
			rb.emplace_back(&v, v);
			swap(u, v);
		}
		if(r - l < 2) return;
		u.m > v.m ? (L ? : L = new LiChaoTree)->insert(u, rb, l, m):
					(R ? : R = new LiChaoTree)->insert(u, rb, m, r);
	}
	int query(int x, int l = 0, int r = LIM + 1) {
		if(r - l < 2) return v(x);
		int m = (l + r) / 2;
		return min(v(x), x < m ? (L ? L->query(x, l, m) : INF) : (R ? R->query(x, m, r) : INF));
	}
} lt;

const int Z = 1e5+1;

int N, S[Z], V[Z], dp[Z];
vector<array<int, 2>> g[Z];

void dfs(int u, int p, int d) {
	vector<pair<Line*, Line>> rb;
	dp[u] = u ? lt.query(V[u]) + S[u] + V[u] * d : int();

	lt.insert(Line(-d, dp[u]), rb);

	// cout << 

	// cerr << u sp p sp d sp size(g[u]) nl;
	// cerr << u sp p sp d nl;

	for(auto &[v, w] : g[u]) if(v != p) {
		// cerr << u sp v sp d sp w nl;
		dfs(v, u, d + w);
	}

	for(int i = size(rb); i--; )
		(*rb[i].first) = rb[i].second;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	for(int i = 1; i < N; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}

	for(int i = 1; i < N; ++i)
		cin >> S[i] >> V[i];

	dfs(0, 0, 0);

	for(int i = 1; i < N; ++i)
		cout << dp[i] << ' ';
}

Compilation message

harbingers.cpp:20:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 |  void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
      |                      ^~~~

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Runtime error 81 ms 50300 KB Memory limit exceeded
4 Runtime error 113 ms 65536 KB Memory limit exceeded
5 Runtime error 124 ms 65540 KB Execution killed with signal 9
6 Runtime error 135 ms 65540 KB Execution killed with signal 9
7 Runtime error 103 ms 34628 KB Memory limit exceeded
8 Runtime error 184 ms 58348 KB Memory limit exceeded
9 Runtime error 122 ms 65540 KB Execution killed with signal 9
10 Runtime error 153 ms 65544 KB Execution killed with signal 9