結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2017-06-09 22:57:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 590 ms / 4,500 ms |
コード長 | 8,684 bytes |
コンパイル時間 | 2,729 ms |
コンパイル使用メモリ | 199,024 KB |
実行使用メモリ | 34,616 KB |
最終ジャッジ日時 | 2024-12-16 06:29:14 |
合計ジャッジ時間 | 9,457 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#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 -> Offsetvector<int> lengths, parents, branches; //Color -> Int, Color -> Color, Color -> Offsetvector<int> parentnodes, depths; //Vertex -> Vertex, Vertex -> Int//vector<FenwickTree>とかを避けて1次元にしたい時に使う//sortednodesの[lefts[v], rights[v])はvのsubtreeとなっているvector<int> sortednodes, offsets; //Index -> Vertex, Color -> Indexvector<int> lefts, rights; //Vertex -> Indexstruct 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);elsehld.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;}