結果

問題 No.529 帰省ラッシュ
ユーザー tomatoma
提出日時 2019-10-11 19:41:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 889 ms / 4,500 ms
コード長 7,706 bytes
コンパイル時間 2,900 ms
コンパイル使用メモリ 215,300 KB
実行使用メモリ 46,060 KB
最終ジャッジ日時 2024-05-03 22:17:43
合計ジャッジ時間 15,222 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 2 ms
5,376 KB
testcase_04 AC 10 ms
5,376 KB
testcase_05 AC 10 ms
5,376 KB
testcase_06 AC 10 ms
5,376 KB
testcase_07 AC 10 ms
5,376 KB
testcase_08 AC 699 ms
26,212 KB
testcase_09 AC 681 ms
25,664 KB
testcase_10 AC 763 ms
30,996 KB
testcase_11 AC 764 ms
31,128 KB
testcase_12 AC 593 ms
26,516 KB
testcase_13 AC 660 ms
46,060 KB
testcase_14 AC 685 ms
30,292 KB
testcase_15 AC 889 ms
34,280 KB
testcase_16 AC 886 ms
34,160 KB
testcase_17 AC 822 ms
42,212 KB
testcase_18 AC 841 ms
42,372 KB
testcase_19 AC 845 ms
40,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;

using Graph = vector<vector<int>>;
struct LowLink {
	vector<int> articulation;
	vector<pair<int, int>> bridge;
	LowLink(const Graph& g) :g(g) {}
	virtual void build() {
		const int N = g.size();
		used.assign(N, 0);
		ord.assign(N, 0);
		low.assign(N, 0);
		int k = 0;
		rep(i, N)if (!used[i])k = dfs(i, k, -1);
	}

protected:
	const Graph& g;
	vector<int> used, ord, low;
	int dfs(int idx, int k, int par) {
		used[idx] = true;
		ord[idx] = k++;
		low[idx] = ord[idx];
		bool is_articulation = false;
		int cnt = 0;

		for (const auto& to : g[idx]) {
			if (!used[to]) {
				++cnt;
				k = dfs(to, k, idx);
				low[idx] = min(low[idx], low[to]);
				is_articulation |= ~par && low[to] >= ord[idx];
				if (ord[idx] < low[to])bridge.emplace_back(minmax(idx, to));
			}
			else if (to != par) {
				low[idx] = min(low[idx], ord[to]);
			}
		}
		is_articulation |= par == -1 && cnt > 1;
		if (is_articulation) {
			articulation.push_back(idx);
		}
		return k;
	}
};
class UnionFind {
public:
	vector<int>rank, parent;
	//初期化
	UnionFind(int size) {
		rank.resize(size, 0);
		parent.resize(size, 0);
		rep(i, size)parent[i] = i;
	}
	//木の根を求める
	int find(int x) {
		if (parent[x] == x)return x;
		else return parent[x] = find(parent[x]);
	}
	//xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])
			parent[x] = y;
		else {
			parent[y] = x;
			if (rank[x] == rank[y])rank[x]++;
		}
	}
	//xとyが同じ集合に属するか否か
	bool same(int x, int y) {
		return (find(x) == find(y));
	}
};
struct TwoEdgeConnectedComponents {
	/* 二重辺連結成分分解
	 * 依存
	 * - LowLink
	 * - UnionFind
	 */
	vector<int> trans; // index -> new index (clustered)
	vector<vector<int>> ngraph; // new index -> new edges (clustered)

	TwoEdgeConnectedComponents(Graph& old_graph) {
		const int N = old_graph.size();
		auto edges = rebuild_edges(old_graph);
		auto bridges = get_bridge(old_graph);

		auto uf = make_uf(N, edges, bridges);
		trans = make_trans(N, uf);
		ngraph = create_ngraph(bridges, trans);
	}
private:
	set<pair<int, int>> rebuild_edges(const Graph& graph) {
		set<pair<int, int>> res;
		rep(i, graph.size())
			for (int j : graph[i])
				if (i < j)
					res.emplace(i, j);
		return res;
	}
	set<pair<int, int>> get_bridge(const Graph& graph) {
		LowLink lowlink(graph);
		lowlink.build();

		set<pair<int, int>> bridges;
		for (auto& bridge : lowlink.bridge) {
			if (bridge.first > bridge.second) {
				swap(bridge.first, bridge.second);
			}
			bridges.insert(bridge);
		}
		return bridges;
	}
	UnionFind make_uf(
		const int N,
		const set<pair<int, int>>& edges,
		const set<pair<int, int>>& bridges
	) {
		UnionFind uf(N);
		for (const auto& edge : edges) {
			if (bridges.find(edge) != bridges.end())continue;
			uf.unite(edge.first, edge.second);
		}
		return uf;
	}
	vector<int> make_trans(
		const int N,
		UnionFind& uf
	) {
		int cnt = 0;
		set<int> st;
		map<int, int> mp;
		rep(i, N)st.insert(uf.find(i));
		for (int num : st)mp[num] = cnt++;

		vector<int> trans;
		rep(i, N)trans.push_back(mp[uf.find(i)]);
		return trans;
	}
	vector<vector<int>> create_ngraph(
		const set<pair<int, int>>& bridges,
		const vector<int>& trans
	) {
		const int M = *max_element(trans.begin(), trans.end()) + 1;
		vector<vector<int>> ngraph(M);
		for (const auto& bridge : bridges) {
			int l = trans[bridge.first];
			int r = trans[bridge.second];
			ngraph[l].push_back(r);
			ngraph[r].push_back(l);
		}
		return ngraph;
	}
};


class SegmentTree {
public:
	int n; // 横幅
	vector<int> data;
	map<int, int> val2idx;

	// init忘れに注意
	SegmentTree() {}
	void init(int n_) {
		n = 1;
		while (n < n_)n <<= 1;
		data.assign(n << 1, -1);
	}
	void set_val(int idx, const int val) {
		val2idx[val] = idx;
		idx += n;
		data[idx] = val;
		while (idx >>= 1) {
			data[idx] = max(data[idx << 1 | 0], data[idx << 1 | 1]);
		}
	}
	int query(int a, int b) {
		// [a,b)
		int vl = 0, vr = 0;
		for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) {
				vl = max(vl, data[l]);
				l++;
			}
			if (r & 1) {
				--r;
				vr = max(data[r], vr);
			}
		}
		return max(vl, vr);
	}
};
struct HLDecomposition {
	using pii = pair<int, int>;
	int n;
	Graph G;
	vector<int> vid, inv, par, depth, subsize, head, prev, next, type;

	HLDecomposition(const Graph& G_) :
		n(G_.size()), G(G_),
		vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
		head(n), prev(n, -1), next(n, -1), type(n) {}
	void build(vector<int> roots = { 0 }) {
		int curtype = 0, pos = 0;
		for (int root : roots) {
			decide_heavy_edge(root);
			reconstruct(root, curtype++, pos);
		}
	}
	void decide_heavy_edge(int root) {
		stack<pii> st;
		par[root] = -1, depth[root] = 0;
		st.emplace(root, 0);
		while (!st.empty()) {
			int now = st.top().first;
			int& way = st.top().second;
			if (way < G[now].size()) {
				int child = G[now][way++];
				if (child == par[now])continue;
				par[child] = now;
				depth[child] = depth[now] + 1;
				st.emplace(child, 0);
			}
			else {
				st.pop();
				int maxsize = 0;
				for (auto child : G[now]) {
					if (child == par[now])continue;
					subsize[now] += subsize[child];
					if (maxsize < subsize[child]) {
						maxsize = subsize[child];
						prev[child] = now;
						next[now] = child;
					}
				}
			}
		}
	}
	void reconstruct(int root, int curtype, int& pos) {
		stack<int> st({ root });
		while (!st.empty()) {
			int start = st.top(); st.pop();
			for (int v = start; v != -1; v = next[v]) {
				type[v] = curtype;
				vid[v] = pos++;
				inv[vid[v]] = v;
				head[v] = start;
				for (auto child : G[v]) {
					if (child != par[v] && child != next[v]) {
						st.push(child);
					}
				}
			}
		}
	}

	// node query [u, v], f([left, right])
	void foreach_nodes(int u, int v, const function<void(int, int)>& f) {
		while (true) {
			if (vid[u] > vid[v])swap(u, v);
			f(max(vid[head[v]], vid[u]), vid[v]);
			if (head[u] != head[v])v = par[head[v]];
			else break;
		}
	}

	// edge query[u,v] f([left, right])
	// seg_node[vid[i]] := edge(par[i] -> i)
	void foreach_edges(int u, int v, const function<void(int, int)>& f) {
		while (true) {
			if (vid[u] > vid[v])swap(u, v);
			if (head[u] != head[v]) {
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			}
			else {
				if (u != v)f(vid[u] + 1, vid[v]);
				break;
			}
		}
	}
	int lca(int u, int v) {
		while (true) {
			if (vid[u] > vid[v])swap(u, v);
			if (head[u] == head[v])return u;
			v = par[head[v]];
		}
	}
};

int main()
{
	int N, M, Q;
	cin >> N >> M >> Q;
	Graph graph(N);
	rep(i, M) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	TwoEdgeConnectedComponents tecc(graph);
	const auto& trans = tecc.trans;
	const auto& ngraph = tecc.ngraph;

	HLDecomposition hld(ngraph); hld.build();
	SegmentTree seg; seg.init(trans.size());
	vector<priority_queue<int>> pqs(trans.size());
	rep(q, Q) {
		int type;
		cin >> type;
		if (type == 1) {
			int u, w;
			cin >> u >> w;
			u--;

			u = trans[u];
			u = hld.vid[u];
			pqs[u].push(w);
			seg.set_val(u, pqs[u].top());
		}
		else {
			int s, t;
			cin >> s >> t;
			s--; t--;

			s = trans[s];
			t = trans[t];
			int res = 0;
			hld.foreach_nodes(s, t, [&](int l, int r) {
				res = max(res, seg.query(l, r + 1));
				});
			if (res == 0) {
				cout << -1 << endl;
			}
			else {
				int idx = seg.val2idx[res];
				pqs[idx].pop();
				seg.set_val(idx, pqs[idx].empty() ? -1 : pqs[idx].top());
				cout << res << endl;
			}
		}
	}

	return 0;
}
0