結果

問題 No.529 帰省ラッシュ
ユーザー QCFiumQCFium
提出日時 2020-01-29 23:05:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 337 ms / 4,500 ms
コード長 4,648 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 197,788 KB
実行使用メモリ 53,480 KB
最終ジャッジ日時 2023-10-14 07:56:35
合計ジャッジ時間 7,210 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,356 KB
testcase_02 AC 1 ms
4,352 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 3 ms
4,352 KB
testcase_05 AC 4 ms
4,352 KB
testcase_06 AC 4 ms
4,348 KB
testcase_07 AC 4 ms
4,352 KB
testcase_08 AC 201 ms
25,504 KB
testcase_09 AC 199 ms
27,568 KB
testcase_10 AC 238 ms
40,720 KB
testcase_11 AC 247 ms
41,088 KB
testcase_12 AC 180 ms
26,216 KB
testcase_13 AC 235 ms
53,480 KB
testcase_14 AC 198 ms
26,124 KB
testcase_15 AC 300 ms
46,316 KB
testcase_16 AC 337 ms
46,256 KB
testcase_17 AC 280 ms
52,680 KB
testcase_18 AC 289 ms
52,256 KB
testcase_19 AC 272 ms
49,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 dfs1(int i, int prev) {
		ord[i] = dfs_cnt++;
		low[i] = ord[i];
		for (auto j : hen[i]) {
			if (!used[j]) {
				used[j] = true;
				dfs1(j, i);
				low[i] = std::min(low[i], low[j]);
				if (low[j] > ord[i]) bridges.push_back({i, j});
			} else if (j != prev) low[i] = std::min(low[i], low[j]);
		}
	}
	std::vector<int> group;
	int group_cnt = 0;
	void dfs2(int i, int prev) {
		if (prev != -1 && low[i] <= ord[prev]) group[i] = group[prev];
		else group[i] = group_cnt++;
		for (auto j : hen[i]) if (group[j] == -1) dfs2(j, i);
	}
	
	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;
		dfs1(0, -1);
		group.resize(n, -1);
		dfs2(0, -1);
		
		std::vector<std::vector<int> > new_hen(group_cnt);
		for (auto i : bridges) {
			new_hen[group[i.first]].push_back(group[i.second]);
			new_hen[group[i.second]].push_back(group[i.first]);
		}
		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]) {
			if (chain[i] > chain[j]) std::swap(i, 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]];
		}
		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;
}
0