Submission #208185

#	Time	Username	Problem	Language	Result	Execution time	Memory
208185		E869120	Magic Tree (CEOI19_magictree)	C++14	100 / 100	845 ms	255196 KiB

magictree

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	long long val, l, r;
};

class DynamicBIT {
public:
	int size_ = 1;
	vector<Node> dat;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.push_back(Node{ 0LL, -1LL, -1LL });
	}
	void add_(int l, int r, long long x, int a, int b, int u) {
		if (l <= a && b <= r) { dat[u].val += x; return; }
		if (b <= l || r <= a) return;

		if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node{ 0LL, -1LL, -1LL }); }
		if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node{ 0LL, -1LL, -1LL }); }
		add_(l, r, x, a, (a + b) >> 1, dat[u].l);
		add_(l, r, x, (a + b) >> 1, b, dat[u].r);
	}
	void add(int l, int r, long long x) {
		add_(l, r, x, 0, size_, 0);
	}
	long long sum(int pos) {
		int ranged = size_, cx = 0; long long s = 0;
		while (ranged >= 2 && cx >= 0) {
			ranged >>= 1; s += dat[cx].val;
			if (pos < ranged) cx = dat[cx].l;
			else { cx = dat[cx].r; pos -= ranged; }
		}
		if (cx != -1) s += dat[cx].val;
		return s;
	}
};

// 入力関連
long long N, P[1 << 18], idx[1 << 18];
long long M, A[1 << 18], B[1 << 18], C[1 << 18];
long long K;
vector<long long> Y;

// グラフ
long long dp[1 << 18];
vector<int> X[100009];

// マージテク
set<long long> Set[100009];
DynamicBIT Z[100009];
int num[100009];

int main() {
	// ステップ 1. 入力
	scanf("%lld%lld%lld", &N, &M, &K);
	for (int i = 2; i <= N; i++) scanf("%lld", &P[i]);
	for (int i = 1; i <= M; i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);

	// ステップ 2. グラフ構築
	for (int i = 1; i <= M; i++) idx[A[i]] = i;
	for (int i = 2; i <= N; i++) X[P[i]].push_back(i);
	for (int i = N; i >= 1; i--) {
		dp[i] = 1;
		for (int j : X[i]) dp[i] += dp[j];
	}

	// ステップ 3. 座標圧縮
	for (int i = 1; i <= M; i++) Y.push_back(B[i]);
	sort(Y.begin(), Y.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for (int i = 1; i <= M; i++) B[i] = (lower_bound(Y.begin(), Y.end(), B[i]) - Y.begin()) + 1;

	// ステップ 4. マージテク
	for (int i = N; i >= 1; i--) {
		if (X[i].size() == 0) {
			num[i] = i;
			Z[i].init(Y.size() + 2);
		}
		else {
			int heavy = -1, maxn = -1;
			for (int j : X[i]) {
				if (maxn < dp[j]) { maxn = dp[j]; heavy = j; num[i] = num[j]; }
			}
			for (int j : X[i]) {
				if (j == heavy) continue;
				auto itr = Set[num[j]].begin(); long long last = 0;
				while (itr != Set[num[j]].end()) {
					long long val = Z[num[j]].sum(*itr);
					Z[num[i]].add(*itr, Y.size() + 2, val - last);
					Set[num[i]].insert(*itr);
					last = val;
					itr++;
				}
			}
		}
		if (idx[i] != 0) {
			int id = idx[i], cx = B[id];
			long long goal = Z[num[i]].sum(B[id]) + C[id];
			while (cx <= Y.size()) {
				long long last = Z[num[i]].sum(cx);
				if (goal - last <= 0LL) break;

				int cl = cx, cr = Y.size() + 2, cm, maxn = cx - 1;
				for (int t = 0; t < 21; t++) {
					cm = (cl + cr) / 2;
					if (Z[num[i]].sum(cm) == last) { maxn = max(maxn, cm); cl = cm; }
					else { cr = cm; }
				}
				Z[num[i]].add(cx, maxn + 1, goal - last);
				cx = maxn + 1;
			}
			Set[num[i]].insert(B[id]);
		}
	}

	cout << Z[num[1]].sum(Y.size() + 1) << endl;
	return 0;
}

Compilation message (stderr)

magictree.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
magictree.cpp: In function 'int main()':
magictree.cpp:106:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (cx <= Y.size()) {
           ~~~^~~~~~~~~~~
magictree.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:63:36: 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("%lld", &P[i]);
                               ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:64:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17