結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 anta
|
| 提出日時 | 2017-06-09 22:57:48 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 434 ms / 4,500 ms |
| コード長 | 8,684 bytes |
| コンパイル時間 | 2,426 ms |
| コンパイル使用メモリ | 196,692 KB |
| 実行使用メモリ | 34,452 KB |
| 最終ジャッジ日時 | 2023-08-22 10:26:37 |
| 合計ジャッジ時間 | 8,294 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,384 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 4 ms
4,380 KB |
| testcase_05 | AC | 4 ms
4,380 KB |
| testcase_06 | AC | 4 ms
4,376 KB |
| testcase_07 | AC | 5 ms
4,376 KB |
| testcase_08 | AC | 272 ms
12,940 KB |
| testcase_09 | AC | 277 ms
15,344 KB |
| testcase_10 | AC | 349 ms
25,148 KB |
| testcase_11 | AC | 369 ms
25,608 KB |
| testcase_12 | AC | 206 ms
12,056 KB |
| testcase_13 | AC | 383 ms
34,452 KB |
| testcase_14 | AC | 227 ms
12,824 KB |
| testcase_15 | AC | 434 ms
28,716 KB |
| testcase_16 | AC | 429 ms
28,776 KB |
| testcase_17 | AC | 334 ms
24,844 KB |
| testcase_18 | AC | 322 ms
24,668 KB |
| testcase_19 | AC | 325 ms
24,304 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;
}