結果

問題 No.529 帰省ラッシュ
ユーザー SHIJOUSHIJOU
提出日時 2020-10-10 16:22:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 586 ms / 4,500 ms
コード長 8,746 bytes
コンパイル時間 2,898 ms
コンパイル使用メモリ 235,576 KB
実行使用メモリ 40,368 KB
最終ジャッジ日時 2023-09-27 21:32:11
合計ジャッジ時間 11,528 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 7 ms
4,376 KB
testcase_05 AC 7 ms
4,376 KB
testcase_06 AC 7 ms
4,376 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 428 ms
21,772 KB
testcase_09 AC 417 ms
20,784 KB
testcase_10 AC 445 ms
24,204 KB
testcase_11 AC 450 ms
24,228 KB
testcase_12 AC 354 ms
21,304 KB
testcase_13 AC 288 ms
40,368 KB
testcase_14 AC 420 ms
29,416 KB
testcase_15 AC 581 ms
26,024 KB
testcase_16 AC 586 ms
26,108 KB
testcase_17 AC 458 ms
37,096 KB
testcase_18 AC 456 ms
37,492 KB
testcase_19 AC 454 ms
34,104 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct TECC {
  struct Edge {
    int to, rev;
    Edge() {}
    Edge(int t, int r):to(t), rev(r) {}
  };
  int n;
  vector<vector<Edge>> G;
  TECC(int n_) : n(n_), G(n_) {}
  void add(int u, int v) {
    G[u].emplace_back(v, int(G[v].size()));
    G[v].emplace_back(u, int(G[u].size())-1);
  }
  pair<int, vector<int>> tecc_ids() {
    int now_ord = 0, group_num = 0;
    vector<int> used, low(n), ord(n, -1), ids(n);
    used.reserve(n);
    auto dfs = [&](auto self, int v)->void {
      low[v] = ord[v] = now_ord++;
      used.push_back(v);
      for(Edge &e:G[v]) if(e.rev != -1) {
        int to = e.to;
        G[to][e.rev].rev = -1;
        e.rev = -1;
        if(ord[to] == -1) {
          self(self, to);
          low[v] = min(low[v], low[to]);
        }
        else {
          low[v] = min(low[v], ord[to]);
        }
      }
      if(low[v] == ord[v]) {
				int u;
        do {
          u = used.back();
          used.pop_back();
          ord[u] = n;
          ids[u] = group_num;
        } while(u != v);
        group_num++;
      }
    };
    for(int i = 0; i < n; i++) {
      if(ord[i] == -1) dfs(dfs, i);
    }
    for(int &x:ids) {
      x = group_num - 1 - x;
    }
    return {group_num, ids};
  }
  vector<vector<int>> tecc() {
    pair<int, vector<int>> ids = tecc_ids();
    int group_num = ids.first;
    vector<int> counts(group_num);
    for(int x:ids.second) counts[x]++;
    vector<vector<int>> groups(group_num);
    for(int i = 0; i < group_num; i++) {
      groups[i].reserve(counts[i]);
    }
    for(int i = 0; i < n; i++) {
      groups[ids.second[i]].push_back(i);
    }
    return groups;
  }
};

struct HLD {
	using Graph = vector<vector<int>>;
	using F = function<void(int, int)>;
	Graph G;
	vector<int> parent, heavy, depth, root, ids, sub, type, inv;
	int _n;
	HLD() {}
	HLD(int n):G(n), parent(n, -1), heavy(n, -1), depth(n), root(n, -1), ids(n), _n(n), sub(n, 1), type(n), inv(n) {}

	void add(int i, int j) {
		G[i].emplace_back(j);
		G[j].emplace_back(i);
	}
	void init(vector<int> roots = vector<int>(1, 0)) {
		int group = 0;
		int pos = 0;
		for(int rt:roots) {
			dfs(rt);
			bfs(rt, group++, pos);
		}
	}
	void dfs(int rt) {
		stack<pair<int, int>> st;
		st.emplace(rt, 0);
		while(!st.empty()) {
			int v = st.top().first;
			int &siz = st.top().second;
			if(siz < int(G[v].size())) {
				int u = G[v][siz++];
				if(u == parent[v]) continue;
				parent[u] = v;
				depth[u] = depth[v]+1;
				st.emplace(u, 0);
			}
			else {
				st.pop();
				int maxSubtree = 0;
				for(int u:G[v]) {
					if(u == parent[v]) continue;
					sub[v] += sub[u];
					if(maxSubtree < sub[u]) maxSubtree = sub[u], heavy[v] = u;
				}
			}
		}
	}
	void bfs(int rt, int group, int &pos) {
		queue<int> que({rt});
		while(!que.empty()) {
			int v = que.front();
			que.pop();
			for(int u = v; u != -1; u = heavy[u]) {
				type[u] = group;
				ids[u] = pos++;
				inv[ids[u]] = u;
				root[u] = v;
				for(int w:G[u]) {
					if(w != parent[u] and w != heavy[u]) que.emplace(w);
				}
			}
		}
	}
	//edge = false -> for_each_vertex, edge = true -> for_each_edge
	void for_each(int u, int v, const F &f, bool edge = false) {
		assert(type[u] == type[v]);
		while(true) {
			if(ids[u] > ids[v]) swap(u, v);
			if(root[u] == root[v]) {
				if(edge) {
					if(u != v) f(ids[u]+1, ids[v]+1);
				}
				else f(ids[u], ids[v]+1);
				break;
			}
			f(ids[root[v]], ids[v]+1);
			v = parent[root[v]];
		}
	}
	int lca(int u, int v) {
		while(true) {
			if(ids[u] > ids[v]) swap(u, v);
			if(root[u] == root[v]) return u;
			v = parent[root[v]];
		}
	}
	int dis(int u, int v) {
		return depth[u] + depth[v] - (depth[lca(u, v)]<<1);
	}
	const int &operator[](int i) const {return ids[i];}
};

template<class T>
struct SegTree {
	using FX = function<T(T, T)>;
	int n, _n;
	FX fx;
	const T ex;
	vector<T> dat;
	SegTree(int n_, FX fx_, T ex_):fx(fx_), ex(ex_), n(1), _n(n_) {
		while(n < n_) n <<= 1;
		dat.assign((n<<1)-1, ex);
	}
	SegTree(vector<T> &v, FX fx_, T ex_):fx(fx_), ex(ex_), n(1), _n(int(v.size())) {
		while(n < _n) n <<= 1;
		dat.assign((n<<1)-1, ex);
		copy(v.begin(), v.end(), dat.begin()+n-1);
		build();
	}
	inline int chld(int k) {return (k<<1)+1;}
	inline int chrd(int k) {return (k<<1)+2;}
	void set(int i, T t) {dat[i+n-1] = t;}
	void build() {
		for(int k = n-2; k >= 0; k--) dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
	}
	void update(int i, T x) {
		i += n-1;
		dat[i] = x;
		while(i) {
			i = (i-1)>>1;
			dat[i] = fx(dat[chld(i)], dat[chrd(i)]);
		}
	}
	inline T query(int a, int b) {return query(a, b, 0, 0, n);}
	T query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return ex;
		if(a <= l && r <= b) return dat[k];
		T vl = query(a, b, chld(k), l, (l+r)>>1);
		T vr = query(a, b, chrd(k), (l+r)>>1, r);
		return fx(vl, vr);
	}
	template<class F>
	int max_right(int l, F f) {
		assert(f(ex));
		if(l == _n) return _n;
		l += n;
		T now = ex;
		do {
			while(~l&1) l >>= 1;
			if(!f(fx(now, dat[l-1]))) {
				while(l < n) {
					l <<= 1;
					if(f(fx(now, dat[l-1]))) {
						now = fx(now, dat[l++ - 1]);
					}
				}
				return l-n;
			}
			now = fx(now, dat[l++ - 1]);
		} while((l & -l) != l);
		return _n;
	}
	template<class F>
	int min_left(int r, F f) {
		assert(f(ex));
		if(r == 0) return 0;
		r += n;
		T now = ex;
		do {
			r--;
			while(r > 1 and r&1) r >>= 1;
			if(!f(fx(dat[r-1], now))) {
				while(r < n) {
					r = chld(r);
					if(f(fx(dat[r-1], now))) {
						now = fx(dat[--r], now);
					}
				}
				return r+1-n;
			}
			now = fx(dat[r-1], now);
		} while((r & -r) != r);
		return 0;
	}
	const T &operator[](int idx) const {return dat[idx+n-1];}
};

#undef _GLIBCXX_DEBUG
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *s) {return to_string(string(s));}
string to_string(bool b) {return b?"true":"false";}
string to_string(vector<bool> v) {
	string res = "{";
	for(int i = 0; i < int(v.size()); i++) {
		if(i) res += ", ";
		res += to_string(v[i]);
	}
	res += "}";
	return res;
}
template<size_t N>
string to_string(bitset<N> v) {
	string res;
	for(size_t i = 0; i < N; i++) res += char('0' + v[i]);
	return res;
}
template<class A, class B>
string to_string(pair<A, B>);
template<class A, class B, class C>
string to_string(tuple<A, B, C>);
template<class A, class B, class C, class D>
string to_string(tuple<A, B, C, D>);
template<class A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for(const auto &x:v) {
		if(!first) res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C>
string to_string(tuple<A, B, C> t) {
	return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}
template<class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> t) {
	return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << ' ' << to_string(H);
	debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 822
#endif

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	TECC tecc(n);
	vector<pair<int, int>> edges(m);
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		tecc.add(--a, --b);
		edges[i] = {a, b};
	}
	auto [gn, blg] = tecc.tecc_ids();
	debug(blg);
	debug(gn);
	HLD hld(gn);
	for(int i = 0; i < m; i++) {
		auto [u, v] = edges[i];
		if(blg[u] == blg[v]) continue;
		hld.add(blg[u], blg[v]);
	}
	hld.init();
	debug(hld.ids);
	debug(hld.root);
	debug(hld.parent);
	SegTree<pair<int, int>> seg(gn, [](const pair<int, int> &a, const pair<int, int> &b) {return max(a, b);}, make_pair(-1, -1));
	auto cor = [&](int i) {return hld[blg[i]];};
	vector<priority_queue<int>> souv(gn);
	while(q--) {
		int type;
		cin >> type;
		if(type == 1) {
			int u, w;
			cin >> u >> w;
			u = cor(u-1);
			debug(u);
			if(souv[u].empty() or souv[u].top() < w) seg.update(u, make_pair(w, u));
			souv[u].emplace(w);
		}
		else {
			int s, t;
			cin >> s >> t;
			pair<int, int> p = make_pair(-1, -1);
			hld.for_each(blg[s-1], blg[t-1], [&](int i, int j)->void {p = max(p, seg.query(i, j));});
			debug(p);
			if(p.first == -1) {
				cout << "-1\n";
			}
			else {
				cout << p.first << '\n';
				int z = p.second;
				souv[z].pop();
				if(souv[z].empty()) seg.update(z, make_pair(-1, -1));
				else seg.update(z, make_pair(souv[z].top(), z));
			}
		}
	}
}
0