#469946 (C++14) No.1038 TreeAddQuery

提出ソース

結果

問題	No.1038 TreeAddQuery
ユーザー	QCFium
提出日時	2020-04-24 23:15:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	4,750 bytes
コンパイル時間	2,591 ms
コンパイル使用メモリ	192,288 KB
実行使用メモリ	147,864 KB
最終ジャッジ日時	2024-04-23 04:14:46
合計ジャッジ時間	22,213 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	11 ms 5,376 KB
testcase_04	AC	13 ms 5,760 KB
testcase_05	AC	11 ms 5,376 KB
testcase_06	AC	10 ms 5,376 KB
testcase_07	AC	14 ms 6,016 KB
testcase_08	AC	729 ms 83,724 KB
testcase_09	AC	854 ms 96,416 KB
testcase_10	AC	882 ms 98,204 KB
testcase_11	AC	889 ms 98,176 KB
testcase_12	AC	911 ms 101,280 KB
testcase_13	AC	1,333 ms 142,336 KB
testcase_14	AC	1,216 ms 129,288 KB
testcase_15	AC	1,185 ms 125,104 KB
testcase_16	AC	1,145 ms 121,524 KB
testcase_17	AC	1,112 ms 119,248 KB
testcase_18	AC	227 ms 32,012 KB
testcase_19	AC	280 ms 36,808 KB
testcase_20	AC	239 ms 36,136 KB
testcase_21	AC	290 ms 42,040 KB
testcase_22	AC	364 ms 53,368 KB
testcase_23	AC	410 ms 58,612 KB
testcase_24	AC	594 ms 81,820 KB
testcase_25	RE	-
testcase_26	AC	862 ms 91,160 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
struct Query {
	int range;
	int weight;
	int id;
};

struct AVL {
	struct Node {
		Node *l;
		Node *r;
		int size;
		int height;
		int key;
		int val;
		int64_t sum;
		Node *fetch() {
			size = 1 + l->size + r->size;
			height = 1 + std::max(l->height, r->height);
			sum = val + l->sum + r->sum;
			return this;
		}
		Node *rotate_l() {
			Node *new_root = r;
			r = new_root->l;
			new_root->l = this;
			return fetch(), new_root->fetch();
		}
		Node *rotate_r() {
			Node *new_root = l;
			l = new_root->r;
			new_root->r = this;
			return fetch(), new_root->fetch();
		}
		int height_diff() { return l->height - r->height; }
		Node *balance() {
			int dif = height_diff();
			if (dif == 2) {
				if (l->height_diff() < 0) l = l->rotate_l();
				return rotate_r();
			} else if (dif == -2) {
				if (r->height_diff() > 0) r = r->rotate_r();
				return rotate_l();
			} else return fetch();
		}
	};
	static Node *nodes, *NONE;
	Node *root = NONE;
	static int head;
	AVL () {
		if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0, 0};
	}
	static Node *insert(Node *node, int key, int val) {
		if (node == NONE) return &(nodes[head++] = {NONE, NONE, 1, 1, key, val, val});
		if (key < node->key) node->l = insert(node->l, key, val);
		else if (key > node->key) node->r = insert(node->r, key, val);
		else assert(0);
		return node->balance();
	}
	static int64_t sum(Node *node, int r) {
		if (node == NONE) return 0;
		if (node->key < r) return node->l->sum + node->val + sum(node->r, r);
		else return sum(node->l, r);
	}
	void insert(int key, int val) { root = insert(root, key, val); }
	int64_t sum(int r) { return sum(root, r); }
	static void reset() { if (head) head = 1; }
	void clear() { root = NONE; }
};
AVL::Node *AVL::nodes = new Node[3000000], *AVL::NONE = nodes;
int AVL::head = 0;



std::vector<std::vector<int> > hen;
std::vector<int> size;
std::vector<bool> alive;
std::vector<std::vector<Query> > qs;
void dfs1(int i, int prev) {
	size[i] = qs[i].size() + 1;
	for (auto j : hen[i]) if (j != prev && alive[j]) {
		dfs1(j, i);
		size[i] += size[j];
	}
}
int centroid(int i) {
	dfs1(i, -1);
	int minimum = (size[i] + 1) / 2;
	while (1) {
		int next = -1;
		for (auto j : hen[i]) if (alive[j] && size[j] < size[i] && size[j] >= minimum) next = j;
		if (next == -1) break;
		i = next;
	}
	return i;
}

std::vector<Query> adds, getqs;
std::vector<int> depth;
void dfs2(int i, int prev) {
	for (auto j : qs[i]) {
		if (j.range >= depth[i]) adds.push_back({j.range - depth[i], j.weight, j.id});
		getqs.push_back({depth[i], 0, j.id});
	}
	for (auto j : hen[i]) if (j != prev && alive[j]) {
		depth[j] = depth[i] + 1;
		dfs2(j, i);
	}
}

std::vector<int64_t> res;
void centroid_rec(int i) {
	// std::cerr << i << " " << centroid(i) << std::endl;
	i = centroid(i);
	std::vector<std::pair<int, Query> > add_all, get_all;
	int group = 0;
	for (auto j : hen[i]) if (alive[j]) {
		adds.clear();
		getqs.clear();
		depth[j] = 1;
		dfs2(j, i);
		for (auto i : adds) add_all.push_back({group, i});
		for (auto i : getqs) get_all.push_back({group, i});
		group++;
	}
	for (auto j : qs[i]) {
		add_all.push_back({group, {j.range, j.weight, j.id}});
		get_all.push_back({group, {0, 0, j.id}});
	}
	std::sort(add_all.begin(), add_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; });
	std::sort(get_all.begin(), get_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; });
	/*
	for (auto i : get_all) std::cerr << "  GET " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl;
	for (auto i : add_all) std::cerr << "  ADD " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl;
	*/
	int head = 0;
	AVL all;
	AVL each[group + 1];
	for (auto j : get_all) {
		while (head < (int) add_all.size() && add_all[head].second.range >= j.second.range) {
			all.insert(add_all[head].second.id, add_all[head].second.weight);
			each[add_all[head].first].insert(add_all[head].second.id, add_all[head].second.weight);
			head++;
		}
		res[j.second.id] += all.sum(j.second.id);
		if (j.first != group) res[j.second.id] -= each[j.first].sum(j.second.id);
	}
	alive[i] = false;
	for (auto j : hen[i]) if (alive[j]) centroid_rec(j);
}

int main() {
	int n = ri();
	int q = ri();
	hen.resize(n);
	for (int i = 1; i < n; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	qs.resize(n);
	for (int i = 0; i < q; i++) {
		int a = ri() - 1;
		int b = ri();
		int c = ri();
		qs[a].push_back({b, c, i});
	}
	size.resize(n);
	alive.resize(n, true);
	depth.resize(n);
	res.resize(q);
	centroid_rec(0);
	for (auto i : res) printf("%" PRId64 "\n", i);
	return 0;
}

yukicoder

結果

テストケース

ソースコード