#441536 (C++14) No.901 K-ary εxtrεεmε

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	polylogK
提出日時	2020-03-09 04:44:44
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	591 ms / 3,000 ms
コード長	7,852 bytes
コンパイル時間	2,939 ms
コンパイル使用メモリ	204,352 KB
実行使用メモリ	47,952 KB
最終ジャッジ日時	2024-11-07 20:43:39
合計ジャッジ時間	16,001 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	236 ms 47,952 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	6 ms 5,248 KB
testcase_03	AC	6 ms 5,248 KB
testcase_04	AC	6 ms 5,248 KB
testcase_05	AC	5 ms 5,248 KB
testcase_06	AC	6 ms 5,248 KB
testcase_07	AC	568 ms 31,048 KB
testcase_08	AC	571 ms 31,036 KB
testcase_09	AC	576 ms 31,040 KB
testcase_10	AC	572 ms 31,040 KB
testcase_11	AC	569 ms 31,048 KB
testcase_12	AC	495 ms 30,924 KB
testcase_13	AC	501 ms 31,044 KB
testcase_14	AC	493 ms 31,048 KB
testcase_15	AC	490 ms 31,052 KB
testcase_16	AC	489 ms 31,044 KB
testcase_17	AC	580 ms 31,048 KB
testcase_18	AC	583 ms 31,048 KB
testcase_19	AC	582 ms 31,032 KB
testcase_20	AC	591 ms 31,044 KB
testcase_21	AC	590 ms 31,044 KB
testcase_22	AC	384 ms 31,052 KB
testcase_23	AC	461 ms 31,040 KB
testcase_24	AC	358 ms 31,048 KB
testcase_25	AC	360 ms 31,044 KB
testcase_26	AC	359 ms 31,048 KB
testcase_27	AC	241 ms 31,048 KB
testcase_28	AC	239 ms 30,920 KB
testcase_29	AC	243 ms 31,060 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

class heavy_light_decomposition {
public:
	using i32 = std::int_fast32_t;
	using u32 = std::uint_fast32_t;

	std::vector<std::vector<u32>> g;
	std::vector<u32> edge_u, edge_v, size, et, in, out, head;
	std::vector<i32> parent, heavy;

private:
	void calc_size(u32 v) {
		size[v] = 1;
		for(int id: g[v]) {
			int to = edge_u[id] ^ edge_v[id] ^ v;
			if(to == parent[v]) continue;
			parent[to] = v;
			calc_size(to);
			size[v] += size[to];

			if(heavy[v] == -1 or size[heavy[v]] < size[to]) heavy[v] = to;
		}
	}
	void calc_et(u32 v) {
		in[v] = et.size();
		et.push_back(v);
		if(heavy[v] != -1) {
			head[heavy[v]] = head[v];
			calc_et(heavy[v]);
		}
		for(int id: g[v]) {	
			int to = edge_u[id] ^ edge_v[id] ^ v;
			if(to == parent[v] or to == heavy[v]) continue;
			head[to] = to;
			calc_et(to);
		}
		out[v] = et.size();
	}

	template<class F>
	void path(i32 x, i32 y, F& process, bool edge) const {
		std::vector<std::pair<u32, u32>> l, r;
		while(true) {
			if(in[x] > in[y]) {
				std::swap(x, y);
				l.swap(r);
			}

			if(head[x] == head[y]) {
				l.emplace_back(in[x] + !!edge, in[y] + 1);
				break;
			}
			l.emplace_back(in[head[y]], in[y] + 1);
			y = parent[head[y]];
		}

		for(auto e: l) process(e.first, e.second);
		for(auto e: r) process(e.first, e.second);
	}
	template<class F>
	void subtree(u32 v, F& process, bool edge) const {
		process(in[v] + !!edge, out[v]);
	}

public:
	heavy_light_decomposition() = default;
	heavy_light_decomposition(heavy_light_decomposition&&) = default;
	heavy_light_decomposition(const heavy_light_decomposition &) = default;

	heavy_light_decomposition(int n)
		: g(n), size(n), in(n), out(n), parent(n, -1), heavy(n, -1), head(n) {}

	void add_edge(int x, int y) {
		g[x].push_back(edge_u.size());
		g[y].push_back(edge_v.size());
		edge_u.push_back(x);
		edge_v.push_back(y);
	}
	void build(u32 root = 0) {
		calc_size(root);
		calc_et(root);
	}

	u32 lca(u32 x, u32 y) const {
		while(true) {
			if(in[x] > in[y]) std::swap(x, y);
			if(head[x] == head[y]) return x;
			y = parent[head[y]];
		}
	}
	
	template<class F>
	void path_node(u32 x, u32 y, const F& process) const { path(x, y, process, false); }
	template<class F>
	void path_edge(u32 x, u32 y, const F& process) const { path(x, y, process, true); }
	template<class F>
	void path(u32 x, u32 y, const F& process) const { path(x, y, process, false); }

	template<class F>
	void subtree_node(u32 v, const F& process) const { subtree(v, process, false); }
	template<class F>
	void subtree_edge(u32 v, const F& process) const { subtree(v, process, true); }
	template<class F>
	void subtree(u32 v, const F& process) const { subtree(v, process, false); }

	u32 index_node(u32 v) const { return in[v]; };
	u32 index_edge(u32 x, u32 y) const { return std::max(in[x], in[y]); };
	u32 index(u32 v) const { return in[v]; };
	
	const u32 operator[](u32 k) const { return in[k]; }
};

template<typename Monoid, typename OperatorMonoid = Monoid>
class lazy_segment_tree {
	using value_type = Monoid;
	using operator_type = OperatorMonoid;
	using size_type = size_t;

	using F = std::function<value_type (value_type, value_type)>;
	using G = std::function<value_type (value_type, operator_type, int, int)>;
	using H = std::function<operator_type (operator_type, operator_type)>;
	
	size_type size_;
	size_type height_;

	F f;
	G g;
	H h;
	value_type id;
	operator_type id_op;
	std::vector<value_type> data;
	std::vector<operator_type> lazy;
	std::vector<size_type> depth;
	
	const size_type get_height(const size_type& size) const {
		size_type height = 1;
		while(1 << height < size) height++;
		return height;
	}
	const size_type base_size() const {
		return 1 << height_;
	}
	const value_type reflect(const size_type & k) {
		if(lazy[k] == id_op) return data[k];
		return g(data[k], lazy[k], 0, 0);
	}
	void eval(const size_type & k) {
		if(lazy[k] == id_op) return;
		lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);
		lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);
		data[k] = reflect(k);
		lazy[k] = id_op;
	}
	void thrust(const size_type & k) {
		for(int i = height_; i; i--) eval(k >> i);
	}
	void recalc(size_type k) {
		while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));
	}
	
	public:
	lazy_segment_tree() {}
	lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :
		size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {
		height_ = get_height(size_);
		data.assign(base_size() << 1, id);
		lazy.assign(base_size() << 1, id_op);
		depth.assign(base_size() << 1, 0);
		for(int i = 0; i < height_ + 1; i++)
			for(int j = (1 << i); j < (1 << (i + 1)); j++)
				depth[j] = i;
	}
	void update(size_type a, size_type b, operator_type x) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) lazy[l] = h(lazy[l], x), l++;
			if(r & 1) --r, lazy[r] = h(lazy[r], x);
		}
		recalc(a);
		recalc(b);
	}
	void change(size_type k, const value_type x) {
		thrust(k += base_size());
		data[k] = x;
		lazy[k] = id_op;
		recalc(k);
	}
	const value_type fold(size_type a, size_type b) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);

		value_type left_value = id;
		value_type right_value = id;
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) left_value = f(left_value, reflect(l++));
			if(r & 1) right_value = f(reflect(--r), right_value);
		}
		return f(left_value, right_value);
	}

	const value_type operator[](const size_type & k) {
		return fold(k, k + 1);
	}
};

struct node {
	int v, v_all;
	
	node() : v(-1), v_all(-1) {}
	node(int v_all) : v(-1), v_all(v_all) {}
	node(int v, int v_all) : v(v), v_all(v_all) {}
};

std::vector<int> depth;
constexpr int dep(const int & k) { return (k < 0 ? -1 : depth[k]); };

int main() {
	int n; scanf("%d", &n);
	std::vector<std::vector<std::pair<int, i64>>> g(n);
	heavy_light_decomposition hld(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);

		g[a].push_back({b, c});
		g[b].push_back({a, c});
		hld.add_edge(a, b);
	}
	hld.build();

	depth.assign(n, 0);
	std::vector<i64> dist(n);
	auto dfs = [&](auto && dfs, int v, int par) -> void {
		for(auto e: g[v]) {
			if(e.first == par) continue;
			dist[e.first] = dist[v] + e.second;
			depth[e.first] = depth[v] + 1;
			dfs(dfs, e.first, v);
		}
	};
	dfs(dfs, 0, -1);
	
	auto calc = [dist, &hld](int u, int v) { return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)]; };
	auto f = [&](node a, node b) {
		return node(
				(dep(a.v) < dep(b.v) ? b.v : a.v),
				(dep(a.v_all) < dep(b.v_all) ? b.v_all : a.v_all));
	};
	auto g_ = [](node a, int b, int l, int r) {
		return node(
				(b ? a.v_all : -1),
				a.v_all);
	};
	auto h = [](int a, int b) { return b; };
	
	lazy_segment_tree<node, int> A(n, f, g_, h,  node(), -1);
	for(int i = 0; i < n; i++) A.change(hld[i], node(i));
	auto kiri = [&A](int l, int r) { A.update(l, r, 1); };
	auto irik = [&A](int l, int r) { A.update(l, r, 0); };

	int q; scanf("%d", &q);
	while(q--) {
		int k; scanf("%d", &k);
				
		i64 ans = 0;
		int c; scanf("%d", &c);
		for(int i = 1; i < k; i++) {
			int v; scanf("%d", &v);
			node tmp = node();
			auto tanpo = [&](int l, int r) { tmp = f(tmp, A.fold(l, r)); };
			hld.path(0, v, tanpo);
			
			int u = (tmp.v == -1 ? c : tmp.v);
			hld.path(u, v, kiri);
			c = hld.lca(v, c);
			ans += calc(v, u);
		}

		A.update(0, n, 0);
		printf("%lld\n", ans);
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード