#422544 (C++14) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	QCFium
提出日時	2020-01-29 20:07:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,111 bytes
コンパイル時間	2,563 ms
コンパイル使用メモリ	201,236 KB
実行使用メモリ	52,428 KB
最終ジャッジ日時	2024-09-16 02:01:41
合計ジャッジ時間	6,080 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	215 ms 52,428 KB
testcase_14	AC	175 ms 24,344 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

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

ソースコード

raw source code

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct TwoDecomp {
	std::vector<std::vector<int> > hen;
	TwoDecomp (const std::vector<std::vector<int> > &hen) : hen(hen) {}
	std::vector<int> low, ord;
	std::vector<bool> used;
	std::vector<std::pair<int, int> > bridges;
	int dfs_cnt = 0;
	void dfs(int i, int prev) {
		ord[i] = dfs_cnt++;
		low[i] = ord[i];
		for (auto j : hen[i]) {
			if (!used[j]) {
				used[j] = true;
				dfs(j, i);
				low[i] = std::min(low[i], low[j]);
			} else if (j != prev) low[i] = std::min(low[i], low[j]);
		}
	}
	std::pair<std::vector<int>, std::vector<std::vector<int> > > decomp() {
		int n = hen.size();
		low.resize(n);
		ord.resize(n);
		used.resize(n);
		used[0] = true;
		dfs(0, -1);
		used.assign(n, false);
		std::vector<int> group(n);
		int group_cnt = 0;
		for (int i = 0; i < n; i++) {
			if (used[i]) continue;
			used[i] = true;
			std::queue<int> que;
			que.push(i);
			while (que.size()) {
				int cur = que.front();
				group[cur] = group_cnt;
				que.pop();
				for (auto j : hen[cur]) {
					if (used[j] || low[j] > ord[cur]) continue;
					used[j] = true;
					que.push(j);
				}
			}
			group_cnt++;
		}
		std::vector<std::vector<int> > new_hen(group_cnt);
		for (int i = 0; i < n; i++) for (auto j : hen[i]) if (group[i] != group[j]) {
			new_hen[group[i]].push_back(group[j]);
		}
		return {group, new_hen};
	}
};

struct SegTree {
	std::vector<std::priority_queue<int> > leaf;
	std::vector<std::pair<int, int> > max;
	int n;
	SegTree () = default;
	SegTree (int n_) {
		for (n = 1; n < n_; n <<= 1);
		leaf.resize(n);
		max.resize(n << 1, {-1, -1});
	}
	void push(int i, int val) {
		leaf[i].push(val);
		for (max[i + n] = {leaf[i].size() ? leaf[i].top() : -1, i}, i += n; i >>= 1; )
			max[i] = std::max(max[i << 1], max[i << 1 | 1]);
	}
	int pop(int i) {
		int val = leaf[i].top();
		leaf[i].pop();
		for (max[i + n] = {leaf[i].size() ? leaf[i].top() : -1, i}, i += n; i >>= 1; )
			max[i] = std::max(max[i << 1], max[i << 1 | 1]);
		return val;
	}
	std::pair<int, int> get_max(int l, int r) {
		int val = -1, index = -1;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) {
				r--;
				if (val < max[r].first) val = max[r].first, index = max[r].second;
			}
			if (l & 1) {
				if (val < max[l].first) val = max[l].first, index = max[l].second;
				l++;
			}
		}
		return {index, val};
	}
};

struct HLDecomp {
	std::vector<std::vector<int> > hen;
	HLDecomp (const std::vector<std::vector<int> > &hen) : hen(hen) {}
	std::vector<int> size, parent;
	void dfs1(int i, int prev) {
		parent[i] = prev;
		if (prev != -1) hen[i].erase(std::find(hen[i].begin(), hen[i].end(), prev));
		for (auto &j : hen[i]) {
			dfs1(j, i);
			size[i] += size[j];
			if (size[j] > size[hen[i][0]]) std::swap(j, hen[i][0]);
		}
	}
	std::vector<int> top, chain, depth_local, chain_sizes{0};
	void dfs2(int i) {
		chain[i] = chain_sizes.size() - 1;
		depth_local[i] = chain_sizes.back()++;
		for (auto j :hen[i]) {
			if (j == hen[i][0]) top[j] = top[i];
			else top[j] = j, chain_sizes.push_back(0);
			dfs2(j);
		}
	}
	std::vector<SegTree> trees;
	void decomp() {
		int n = hen.size();
		size.resize(n, 1);
		parent.resize(n);
		dfs1(0, -1);
		top.resize(n);
		chain.resize(n);
		depth_local.resize(n);
		dfs2(0);
		int m = chain_sizes.size();
		trees.resize(m);
		for (int i = 0; i < m; i++) trees[i] = SegTree(chain_sizes[i]);
	}
	void push(int i, int val) {
		trees[chain[i]].push(depth_local[i], val);
	}
	int pop(int i, int j) {
		int max = -1, max_chain = -1, max_depth = -1;
		while (chain[i] > chain[j]) {
			auto tmp = trees[chain[i]].get_max(0, depth_local[i] + 1);
			if (max < tmp.second) max = tmp.second, max_chain = chain[i], max_depth = tmp.first;
			i = parent[top[i]];
		}
		while (chain[i] < chain[j]) {
			auto tmp = trees[chain[j]].get_max(0, depth_local[j] + 1);
			if (max < tmp.second) max = tmp.second, max_chain = chain[j], max_depth = tmp.first;
			j = parent[top[j]];
		}
		while (chain[i] > chain[j]) {
			auto tmp = trees[chain[i]].get_max(0, depth_local[i] + 1);
			if (max < tmp.second) max = tmp.second, max_chain = chain[i], max_depth = tmp.first;
			i = parent[top[i]];
		}
		if (depth_local[i] > depth_local[j]) std::swap(i, j);
		auto tmp = trees[chain[i]].get_max(depth_local[i], depth_local[j] + 1);
		if (max < tmp.second) max = tmp.second, max_chain = chain[i], max_depth = tmp.first;
		
		if (max == -1) return -1;
		trees[max_chain].pop(max_depth);
		return max;
	}
};

int main() {
	int n = ri(), m = ri(), q = ri();
	std::vector<std::vector<int> > org_hen(n);
	for (int i = 0; i < m; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		org_hen[a].push_back(b);
		org_hen[b].push_back(a);
	}
	TwoDecomp two_decomper(org_hen);
	auto decomped = two_decomper.decomp();
	auto group = decomped.first;
	auto hen = decomped.second;
	
	HLDecomp hl_decomper(hen);
	hl_decomper.decomp();
	for (int i = 0; i < q; i++) {
		int t = ri();
		int x = ri();
		int y = ri();
		if (t == 1) hl_decomper.push(group[x - 1], y);
		else printf("%d\n", hl_decomper.pop(group[x - 1], group[y - 1]));
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード