結果

問題 No.529 帰省ラッシュ
ユーザー kazumakazuma
提出日時 2017-06-25 15:02:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 783 ms / 4,500 ms
コード長 5,530 bytes
コンパイル時間 2,336 ms
コンパイル使用メモリ 196,028 KB
実行使用メモリ 37,268 KB
最終ジャッジ日時 2023-08-22 11:03:19
合計ジャッジ時間 11,006 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,388 KB
testcase_04 AC 9 ms
4,380 KB
testcase_05 AC 9 ms
4,380 KB
testcase_06 AC 8 ms
4,380 KB
testcase_07 AC 9 ms
4,380 KB
testcase_08 AC 535 ms
21,036 KB
testcase_09 AC 521 ms
19,680 KB
testcase_10 AC 580 ms
23,924 KB
testcase_11 AC 568 ms
24,012 KB
testcase_12 AC 433 ms
19,376 KB
testcase_13 AC 379 ms
37,268 KB
testcase_14 AC 509 ms
26,788 KB
testcase_15 AC 783 ms
26,228 KB
testcase_16 AC 771 ms
26,312 KB
testcase_17 AC 579 ms
34,944 KB
testcase_18 AC 572 ms
34,896 KB
testcase_19 AC 570 ms
32,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

struct Edge {
	int from, to;
	Edge(int f, int t) {
		from = f;
		to = t;
	}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;
pair<vector<int>, Edges> bridge(const Graph& g) {
	const int n = g.size();
	int idx = 0, s = 0, t = 0, k = 0;
	vector<int>ord(n, -1), onS(n), stk(n), roots(n), cmp(n);
	Edges brdg;
	function<void(int, int)> dfs = [&](int v, int u) {
		ord[v] = idx++;
		stk[s++] = v;
		onS[v] = true;
		roots[t++] = v;
		for (auto& e : g[v]) {
			int w = e.to;
			if (ord[w] == -1)dfs(w, v);
			else if (u != w && onS[w])
				while (ord[roots[t - 1]]>ord[w])--t;
		}
		if (v == roots[t - 1]) {
			brdg.emplace_back(u, v);
			while (true) {
				int w = stk[--s];
				onS[w] = false;
				cmp[w] = k;
				if (v == w)break;
			}
			--t;
			++k;
		}
	};
	for (int u = 0; u<n; ++u) {
		if (ord[u] == -1) {
			dfs(u, n);
			brdg.pop_back();
		}
	}
	return make_pair(cmp, brdg);
}

class HLDecomposition {
	vector<vector<int>> g;
	vector<int> vid, head, heavy, parent, depth, inv;
	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			depth[next] = depth[curr] + 1;
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}
	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				inv[vid[i]] = i;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}
public:
	HLDecomposition(int n)
		: g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		bfs();
	}
	void for_each(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		f(max(vid[head[v]], vid[u]), vid[v]);
		if (head[u] != head[v]) for_each(u, parent[head[v]], f);
	}
	void for_each_directed(int u, int v, function<void(int, int, int)> f) {
		if (vid[u] > vid[v]) {
			f(max(vid[head[u]], vid[v]), vid[u], 1);
			if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f);
		}
		else {
			f(max(vid[head[v]], vid[u]), vid[v], 0);
			if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f);
		}
	}
	void for_each_edge(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		if (head[u] != head[v]) {
			f(vid[head[v]], vid[v]);
			for_each_edge(u, parent[head[v]], f);
		}
		else {
			if (u != v) f(vid[u] + 1, vid[v]);
		}
	}
	int ancestor(int u, int d) {
		while (true) {
			if (depth[head[u]] > depth[u] - d) {
				d -= depth[u] - depth[head[u]] + 1;
				if (head[u] == 0) return 0;
				u = parent[head[u]];
			}
			else {
				return inv[vid[u] - d];
			}
		}
	}
	int lca(int u, int v) {
		if (vid[u] > vid[v]) swap(u, v);
		if (head[u] == head[v]) return u;
		return lca(u, parent[head[v]]);
	}
	int distance(int u, int v) {
		return depth[u] + depth[v] - 2 * depth[lca(u, v)];
	}
};

template <typename T>
class SegmentTree {
	using func_t = function<T(T, T)>;
	const int n;
	const T id;
	func_t merge;
	vector<T> data;
	int size(int n) {
		int res;
		for (res = 1; res < n; res <<= 1);
		return res;
	}
	T sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) return data[node];
		return merge(sub(l, r, node * 2, lb, (lb + ub) / 2), sub(l, r, node * 2 + 1, (lb + ub) / 2, ub));
	}
public:
	SegmentTree(int n_, T id_, func_t merge_) :
		n(size(n_)), id(id_), merge(merge_), data(size(n_) * 2, id_) {}
	void Init(const vector<T>& data_) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n] = data_[i];
		for (int i = n - 1; i >= 0; i--)
			data[i] = merge(data[i * 2], data[i * 2 + 1]);
	}
	void Update(int p, T val) {
		p += n;
		data[p] = val;
		while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]);
	}
	void Add(int p, T val) {
		p += n;
		data[p] += val;
		while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]);
	}
	T Find(int i) {
		return data[i + n];
	}
	T Find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

const function<P(P, P)> merg = [](P l, P r) { return l.first >= r.first ? l : r; };

int main()
{
	int N, M, Q, com, X, Y;
	cin >> N >> M >> Q;
	Graph G(N);
	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i]; A[i]--; B[i]--;
		G[A[i]].push_back(Edge(A[i], B[i]));
		G[B[i]].push_back(Edge(B[i], A[i]));
	}
	auto bri = bridge(G);
	int V = 0;
	for (int i = 0; i < N; i++) {
		V = max(V, bri.first[i]);
	}
	V++;
	HLDecomposition hl(V);
	for (auto e : bri.second) {
		hl.add(bri.first[e.from], bri.first[e.to]);
	}
	hl.build();
	SegmentTree<P> st(V, P(), merg);
	vector<priority_queue<int>> W(V);
	while (Q--) {
		cin >> com >> X >> Y;
		if (com == 1) {
			X--;
			X = bri.first[X];
			W[X].push(Y);
			hl.for_each(X, X, [&](int l, int r) {
				st.Update(l, P(W[X].top(), X));
			});
		}
		else {
			X--; Y--;
			X = bri.first[X]; Y = bri.first[Y];
			P res;
			hl.for_each(X, Y, [&](int l, int r) {
				res = merg(res, st.Find(l, r));
			});
			if (res == P()) {
				printf("%d\n", -1);
				continue;
			}
			printf("%d\n", res.first);
			W[res.second].pop();
			P val = W[res.second].empty() ? P() : P(W[res.second].top(), res.second);
			hl.for_each(res.second, res.second, [&](int l, int r) {
				st.Update(l, val);
			});
		}
	}
	return 0;
}
0