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

• 問題: No.529 帰省ラッシュ
• ユーザー: anta
• 提出日時: 2017-06-09 22:57:48
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 344 ms / 4,500 ms
• コード長: 8,684 bytes
• コンパイル時間: 2,509 ms
• コンパイル使用メモリ: 198,300 KB
• 実行使用メモリ: 34,748 KB
• 最終ジャッジ日時: 2024-05-09 16:06:12
• 合計ジャッジ時間: 7,196 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	5 ms; 5,376 KB
testcase_05	AC	5 ms; 5,376 KB
testcase_06	AC	4 ms; 5,376 KB
testcase_07	AC	5 ms; 5,376 KB
testcase_08	AC	235 ms; 13,224 KB
testcase_09	AC	235 ms; 15,624 KB
testcase_10	AC	269 ms; 25,368 KB
testcase_11	AC	274 ms; 25,836 KB
testcase_12	AC	182 ms; 12,356 KB
testcase_13	AC	288 ms; 34,748 KB
testcase_14	AC	194 ms; 12,988 KB
testcase_15	AC	344 ms; 28,896 KB
testcase_16	AC	328 ms; 28,776 KB
testcase_17	AC	251 ms; 25,044 KB
testcase_18	AC	256 ms; 24,832 KB
testcase_19	AC	254 ms; 24,672 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
#define each(it,o) for(auto it = (o).begin(); it != (o).end(); ++ it)

struct State {
	int i, parent, j; bool b;
	State() { }
	State(int i_, int parent_, int j_, bool b_) : i(i_), parent(parent_), j(j_), b(b_) { }
};
void compute_lowlinks(const vector<vector<int> > &g, vector<int> &ord, vector<int> &low) {
	int n = g.size();
	ord.assign(n, -1); low.assign(n, -1);
	int order = 0;
	vector<State> stk;
	for (int ii = 0; ii < n; ii ++) if (ord[ii] == -1) {
		stk.push_back(State(ii, -1, 0, false));
		while (!stk.empty()) {
			State s = stk.back(); stk.pop_back();
			if (s.j == 0)
				low[s.i] = ord[s.i] = order ++;
			if (s.b)
				low[s.i] = min(low[s.i], low[g[s.i][s.j - 1]]);
			if (g[s.i].size() == s.j)
				continue;
			int v = g[s.i][s.j];
			if (ord[v] == -1) {
				stk.push_back(State(s.i, s.parent, s.j + 1, true));
				stk.push_back(State(v, s.i, 0, false));
			} else if (v != s.parent || (s.j + 1 != g[s.i].size() && g[s.i][s.j + 1] == v)) {
				stk.push_back(State(s.i, s.parent, s.j + 1, false));
				low[s.i] = min(low[s.i], ord[v]);
			} else {
				stk.push_back(State(s.i, s.parent, s.j + 1, false));
			}
		}
	}
}

inline bool is_bridge_edge(int i, int j, const vector<int> &ord, const vector<int> &low) {
	return ord[i] < low[j] || ord[j] < low[i];
}

struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int two_edge_connected_components(const vector<vector<int>> &g, vector<int> &color, vector<int> &ord, vector<int> &low) {
	int n = g.size();
	compute_lowlinks(g, ord, low);
	int colors = 0;
	color.assign(n, -1);
	UnionFind uf; uf.init(n);
	rep(i, n) each(j, g[i]) if (!is_bridge_edge(i, *j, ord, low))
		uf.unionSet(i, *j);
	rep(i, n) if (uf.root(i) == i)
		color[i] = colors ++;
	rep(i, n)
		color[i] = color[uf.root(i)];
	return colors;
}

struct HeavyLightDecomposition {
	vector<int> colors, positions;	//Vertex -> Color, Vertex -> Offset
	vector<int> lengths, parents, branches;	//Color -> Int, Color -> Color, Color -> Offset
	vector<int> parentnodes, depths;	//Vertex -> Vertex, Vertex -> Int
										//vector<FenwickTree>とかを避けて1次元にしたい時に使う
										//sortednodesの[lefts[v], rights[v])はvのsubtreeとなっている
	vector<int> sortednodes, offsets;	//Index -> Vertex, Color -> Index
	vector<int> lefts, rights;	//Vertex -> Index

	struct BuildDFSState {
		int i, len, parent;
		BuildDFSState() { }
		BuildDFSState(int i_, int l, int p) : i(i_), len(l), parent(p) { }
	};

	//両方の辺があってもいいし、親から子への辺だけでもよい
	void build(const vector<vi> &g, int root) {
		int n = g.size();

		colors.assign(n, -1); positions.assign(n, -1);
		lengths.clear(); parents.clear(); branches.clear();
		parentnodes.assign(n, -1); depths.assign(n, -1);

		sortednodes.clear(); offsets.clear();
		lefts.assign(n, -1); rights.assign(n, -1);

		vector<int> subtreesizes;
		measure(g, root, subtreesizes);

		typedef BuildDFSState State;
		depths[root] = 0;
		vector<State> s;
		s.push_back(State(root, 0, -1));
		while (!s.empty()) {
			State t = s.back(); s.pop_back();
			int i = t.i, len = t.len;
			int index = sortednodes.size();
			int color = lengths.size();

			if (t.parent == -3) {
				rights[i] = index;
				continue;
			}

			if (t.parent != -2) {
				assert(parents.size() == color);
				parents.push_back(t.parent);
				branches.push_back(len);
				offsets.push_back(index);
				len = 0;
			}
			colors[i] = color;
			positions[i] = len;

			lefts[i] = index;
			sortednodes.push_back(i);

			int maxsize = -1, maxj = -1;
			each(j, g[i]) if (colors[*j] == -1) {
				if (maxsize < subtreesizes[*j]) {
					maxsize = subtreesizes[*j];
					maxj = *j;
				}
				parentnodes[*j] = i;
				depths[*j] = depths[i] + 1;
			}
			s.push_back(State(i, -1, -3));
			if (maxj == -1) {
				lengths.push_back(len + 1);
			} else {
				each(j, g[i]) if (colors[*j] == -1 && *j != maxj)
					s.push_back(State(*j, len, color));
				s.push_back(State(maxj, len + 1, -2));
			}
		}
	}

	void get(int v, int &c, int &p) const {
		c = colors[v]; p = positions[v];
	}
	bool go_up(int &c, int &p) const {
		p = branches[c]; c = parents[c];
		return c != -1;
	}

	inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
	inline const int *nodesEnd(int c) const { return &sortednodes[0] + (c + 1 == offsets.size() ? sortednodes.size() : offsets[c + 1]); }

private:
	void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
		out_subtreesizes.assign(g.size(), -1);
		vector<int> s;
		s.push_back(root);
		while (!s.empty()) {
			int i = s.back(); s.pop_back();
			if (out_subtreesizes[i] == -2) {
				int s = 1;
				each(j, g[i]) if (out_subtreesizes[*j] != -2)
					s += out_subtreesizes[*j];
				out_subtreesizes[i] = s;
			} else {
				s.push_back(i);
				each(j, g[i]) if (out_subtreesizes[*j] == -1)
					s.push_back(*j);
				out_subtreesizes[i] = -2;
			}
		}
	}
};

struct DynamicRMQ {
	typedef int Val;
	int n;
	vector<Val> d;
	void init(int nmin) {
		for (n = 1; n < nmin; n *= 2);
		d.assign(n * 2, -INF);
	}
	void update(int i, Val x) {
		d[n + i] = x;
		for (int k = (n + i) / 2; k > 0; k >>= 1)
			d[k] = max(d[k * 2], d[k * 2 + 1]);
	}
	Val get(int i) const { return d[n + i]; }
	//[l, r)
	Val query(int l, int r) const {
		Val m = -INF;
		for (; l && l + (l&-l) <= r; l += l&-l)
			m = max(m, d[(n + l) / (l&-l)]);
		for (; l < r; r -= r&-r)
			m = max(m, d[(n + r) / (r&-r) - 1]);
		return m;
	}
};

int lowest_common_ancestor(const HeavyLightDecomposition &hld, int x, int y) {
	int cx, px, cy, py;
	hld.get(x, cx, px);
	hld.get(y, cy, py);
	while (cx != cy) {
		if (hld.depths[*hld.nodesBegin(cx)] < hld.depths[*hld.nodesBegin(cy)])
			hld.go_up(cy, py);
		else
			hld.go_up(cx, px);
	}
	return hld.nodesBegin(cx)[min(px, py)];
}

int main() {
	int N; int M; int Q;
	while (~scanf("%d%d%d", &N, &M, &Q)) {
		vector<vector<int> > g(N);
		for (int i = 0; i < M; ++ i) {
			int u, v;
			scanf("%d%d", &u, &v), -- u, -- v;
			if (u != v) {
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
		rep(i,N)
			sort(g[i].begin(), g[i].end());
		vector<int> color, ord, low;
		int C = two_edge_connected_components(g, color, ord, low);
		vector<vi> tree(C);
		int E = 0;
		rep(i, N) for (int j : g[i]) if (color[i] != color[j]) {
			tree[color[i]].push_back(color[j]);
			++ E;
			//cerr << i + 1 << " " << j + 1;
		}
		assert(E == (C - 1) * 2);
		HeavyLightDecomposition hld;
		hld.build(tree, 0);
		vector<DynamicRMQ> rmqs(hld.lengths.size());
		rep(i, hld.lengths.size())
			rmqs[i].init(hld.lengths[i]);
		vector<priority_queue<int>> weights(C);
		map<int, int> valmap;
		for (int ii = 0; ii < Q; ++ ii) {
			int ty;
			scanf("%d", &ty);
			if (ty == 1) {
				int u; int w;
				scanf("%d%d", &u, &w), -- u;
				u = color[u];
				valmap[w] = u;
				weights[u].push(w);
				int c, p;
				hld.get(u, c, p);
				rmqs[c].update(p, weights[u].top());
			} else if (ty == 2) {
				int u; int v;
				scanf("%d%d", &u, &v), -- u, -- v;
				u = color[u];
				v = color[v];
				int ans = -1;
				int w = lowest_common_ancestor(hld, u, v), wc, wp;
				hld.get(w, wc, wp);
				rep(uv, 2) {
					int c, p;
					hld.get(uv == 0 ? u : v, c, p);
					while (1) {
						int top = c == wc ? wp + uv : 0;
						int val = rmqs[c].query(top, p + 1);
						amax(ans, val);
						if (c == wc) break;
						hld.go_up(c, p);
					}
				}
				printf("%d\n", ans);
				if (ans != -1) {
					assert(valmap.count(ans));
					int x = valmap[ans], xc, xp;
					assert(!weights[x].empty() && weights[x].top() == ans);
					weights[x].pop();
					hld.get(x, xc, xp);
					rmqs[xc].update(xp, weights[x].empty() ? -INF : weights[x].top());
					valmap.erase(ans);
				}
			} else abort();
		}
	}
	return 0;
}