#537724 (C++14) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	square1001
提出日時	2020-08-22 15:14:54
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	357 ms / 3,000 ms
コード長	4,601 bytes
コンパイル時間	1,378 ms
コンパイル使用メモリ	93,832 KB
実行使用メモリ	34,300 KB
最終ジャッジ日時	2024-04-23 17:54:28
合計ジャッジ時間	9,980 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	76 ms 29,324 KB
testcase_08	AC	105 ms 12,668 KB
testcase_09	AC	146 ms 20,156 KB
testcase_10	AC	199 ms 19,428 KB
testcase_11	AC	115 ms 8,704 KB
testcase_12	AC	91 ms 6,016 KB
testcase_13	AC	69 ms 13,824 KB
testcase_14	AC	190 ms 13,952 KB
testcase_15	AC	124 ms 8,192 KB
testcase_16	AC	228 ms 22,688 KB
testcase_17	AC	255 ms 22,924 KB
testcase_18	AC	84 ms 9,472 KB
testcase_19	AC	203 ms 19,512 KB
testcase_20	AC	42 ms 8,320 KB
testcase_21	AC	111 ms 5,376 KB
testcase_22	AC	14 ms 5,376 KB
testcase_23	AC	201 ms 14,912 KB
testcase_24	AC	155 ms 14,624 KB
testcase_25	AC	96 ms 11,136 KB
testcase_26	AC	174 ms 11,520 KB
testcase_27	AC	224 ms 21,228 KB
testcase_28	AC	150 ms 12,652 KB
testcase_29	AC	120 ms 14,300 KB
testcase_30	AC	105 ms 15,984 KB
testcase_31	AC	91 ms 13,056 KB
testcase_32	AC	72 ms 5,376 KB
testcase_33	AC	56 ms 11,264 KB
testcase_34	AC	343 ms 23,884 KB
testcase_35	AC	349 ms 23,880 KB
testcase_36	AC	357 ms 23,880 KB
testcase_37	AC	333 ms 23,876 KB
testcase_38	AC	344 ms 23,900 KB
testcase_39	AC	340 ms 23,900 KB
testcase_40	AC	260 ms 34,300 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB

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

ソースコード

raw source code

#ifndef CLASS_FENWICKTREE
#define CLASS_FENWICKTREE

#include <vector>
#include <cassert>
#include <cstddef>

template <class type>
class fenwick_tree {
private:
	std::size_t n, sz;
	std::vector<type> val;
public:
	fenwick_tree() : n(0), sz(0) {};
	fenwick_tree(std::size_t n_) : n(n_) {
		sz = 1; while (sz < n) sz *= 2;
		val = std::vector<type>(sz + 1);
	}
	template <class InputIterator>
	fenwick_tree(InputIterator first, InputIterator last) : n(last - first) {
		sz = 1; while (sz < n) sz *= 2;
		val = std::vector<type>(sz + 1);
		std::size_t cur = 0;
		for (InputIterator it = first; it != last; ++it) val[++cur] += *it;
		for (std::size_t i = 1; i < sz; ++i) val[i + (i & ~(i - 1))] += val[i];
	}
	void add(std::size_t pos, type delta) {
		for (std::size_t i = pos + 1; i <= sz; i += i & ~(i - 1)) {
			val[i] += delta;
		}
	}
	type getsum(std::size_t r) const {
		assert(0 <= r && r <= n);
		type ans = 0;
		for (std::size_t i = r; i >= 1; i -= i & ~(i - 1)) {
			ans += val[i];
		}
		return ans;
	}
	type getsum(std::size_t l, std::size_t r) const {
		assert(0 <= l && l <= r && r <= n);
		return getsum(r) - getsum(l);
	}
	std::size_t binary_search(type threshold) const {
		std::size_t ans = 0;
		for (std::size_t i = (sz >> 1); i >= 1; i >>= 1) {
			if (threshold >= val[ans + i]) {
				threshold -= val[ans + i];
				ans += i;
			}
		}
		return ans;
	}
};

#endif // CLASS_FENWICKTREE

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int> C(K);
	for (int i = 0; i < K; ++i) {
		cin >> C[i]; --C[i];
	}
	vector<vector<int> > G(N);
	for (int i = 0; i < N - 1; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	// step #1. build tree
	vector<vector<int> > child(N);
	vector<int> p(N), subtree(N, 1), depth(N);
	function<void(int, int)> build_tree_1 = [&](int pos, int pre) {
		p[pos] = pre;
		for (int i : G[pos]) {
			if (i != pre) {
				child[pos].push_back(i);
				depth[i] = depth[pos] + 1;
				build_tree_1(i, pos);
				subtree[pos] += subtree[i];
			}
		}
		sort(child[pos].begin(), child[pos].end(), [&](int i, int j) { return subtree[i] > subtree[j]; });
	};
	build_tree_1(0, 0);
	int track = 0;
	vector<int> lp(N), rp(N);
	function<void(int, int)> build_tree_2 = [&](int pos, int pre) {
		lp[pos] = track++;
		for (int i : child[pos]) {
			build_tree_2(i, pos);
		}
		rp[pos] = track;
	};
	build_tree_2(0, 0);
	// step #2. prepare for heavy-light decomposition
	int bits = 1;
	while ((1 << bits) < N) ++bits;
	vector<vector<int> > par(bits, vector<int>(N));
	par[0] = p;
	for (int i = 1; i < bits; ++i) {
		for (int j = 0; j < N; ++j) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	fenwick_tree<long long> fen1(N), fen2(N);
	function<void(int, int, long long)> range_add = [&](int l, int r, long long x) {
		fen1.add(l, x);
		fen1.add(r, -x);
		fen2.add(l, -l * x);
		fen2.add(r, r * x);
	};
	function<long long(int, int)> range_sum = [&](int l, int r) {
		return fen1.getsum(r) * r - fen1.getsum(l) * l + fen2.getsum(l, r);
	};
	function<void(int, int)> add = [&](int pos, int val) {
		int cdepth = depth[pos];
		while (true) {
			int nxt = pos, ndepth = cdepth;
			for (int i = bits - 1; i >= 0; --i) {
				if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth + (1 << i))) {
					ndepth -= (1 << i);
					nxt = par[i][nxt];
				}
			}
			range_add(lp[nxt], lp[pos] + 1, val);
			if (nxt == 0) break;
			pos = par[0][nxt];
			cdepth = ndepth - 1;
		}
	};
	function<long long(int)> sum = [&](int pos) {
		int cdepth = depth[pos];
		long long res = 0;
		while (true) {
			int nxt = pos, ndepth = cdepth;
			for (int i = bits - 1; i >= 0; --i) {
				if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth + (1 << i))) {
					ndepth -= (1 << i);
					nxt = par[i][nxt];
				}
			}
			res += range_sum(lp[nxt], lp[pos] + 1);
			if (nxt == 0) break;
			pos = par[0][nxt];
			cdepth = ndepth - 1;
		}
		return res;
	};
	// step #3. solve
	long long basic = 0;
	for (int i = 0; i < K; ++i) {
		add(C[i], 1);
		basic += depth[C[i]];
	}
	long long ans = 0;
	for (int i = 0; i < Q; ++i) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int x, y;
			cin >> x >> y; --x, --y;
			add(C[x], -1);
			basic -= depth[C[x]];
			C[x] = y;
			add(C[x], 1);
			basic += depth[C[x]];
		}
		else {
			int x;
			cin >> x; --x;
			long long ans = 1LL * depth[x] * K + basic;
			long long res = sum(x) - K;
			ans -= res * 2;
			cout << ans << '\n';
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード