結果
問題 | No.529 帰省ラッシュ |
ユーザー |
|
提出日時 | 2024-08-18 19:05:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 4,500 ms |
コード長 | 2,447 bytes |
コンパイル時間 | 1,976 ms |
コンパイル使用メモリ | 179,884 KB |
実行使用メモリ | 42,564 KB |
最終ジャッジ日時 | 2024-08-18 19:05:51 |
合計ジャッジ時間 | 7,060 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using LL = long long;const int N = 1e5 + 7;const int T = 1 << 18 | 7;int n, m, q, c, max[T];std::map<int, int> pos;std::vector<int> tr[N], gr[N];std::priority_queue<int> w[N];int stk[N], *stp = stk, dfn[N], low[N], cnt, bel[N];int dep[N], fa[N], sz[N], son[N];int seq[N], top[N], tot;void tarjan(int x, int y) {*++stp = x;dfn[x] = low[x] = ++cnt;for(int v: gr[x])if(v != y)if(!dfn[v]) {tarjan(v, x);low[x] = std::min(low[x], low[v]);}elselow[x] = std::min(low[x], dfn[v]);if(low[x] == dfn[x]) {while(*stp != x)bel[*stp--] = x;bel[*stp--] = x;}}void dfs(int x) {sz[x] = 1;for(int v: tr[x]) {fa[v] = x;dep[v] = dep[x] + 1;dfs(v);sz[x] += sz[v];if(sz[v] > sz[son[x]])son[x] = v;}}void dfs(int x, int y) {top[x] = y;seq[x] = ++tot;if(son[x])dfs(son[x], y);for(int v: tr[x])if(v != son[x])dfs(v, v);}void modify(int x, int y) {max[x += c] = y;while(x >>= 1)max[x] = std::max(max[x << 1], max[x << 1 | 1]);}int ask(int l, int r) {int ret = -1;for(l += c - 1, r += c + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {if(~l & 1) ret = std::max(ret, max[l ^ 1]);if( r & 1) ret = std::max(ret, max[r ^ 1]);}return ret;}void mfy(int x, int y) {pos[y] = bel[x];w[bel[x]].push(y);modify(seq[bel[x]], w[bel[x]].top());}int qry(int x, int y) {x = bel[x];y = bel[y];int ret = -1;while(top[x] != top[y]) {if(dep[top[x]] < dep[top[y]])std::swap(x, y);ret = std::max(ret, ask(seq[top[x]], seq[x]));x = fa[top[x]];}if(dep[x] > dep[y])std::swap(x, y);ret = std::max(ret, ask(seq[x], seq[y]));if(ret != -1) {w[pos[ret]].pop();modify(seq[pos[ret]], w[pos[ret]].empty() ? -1 : w[pos[ret]].top());}return ret;}int main() {scanf("%d%d%d", &n, &m, &q);for(int i = 1, x, y; i <= m; ++i) {scanf("%d%d", &x, &y);gr[x].push_back(y);gr[y].push_back(x);}tarjan(1, 0);for(int i = 1; i <= n; ++i)for(int j: gr[i])if(bel[i] != bel[j] && dfn[i] < dfn[j])tr[bel[i]].push_back(bel[j]);dfs(1);dfs(1, 1);memset(max, -1, sizeof max);for(c = tot + 2; c & c - 1; c += c & -c) ;while(q--) {int t, x, y;scanf("%d%d%d", &t, &x, &y);if(t == 1)mfy(x, y);elseprintf("%d\n", qry(x, y));}return 0;}