結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2016-11-01 16:43:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 660 ms / 4,500 ms |
コード長 | 7,302 bytes |
コンパイル時間 | 2,603 ms |
コンパイル使用メモリ | 202,868 KB |
実行使用メモリ | 54,016 KB |
最終ジャッジ日時 | 2024-12-16 02:15:26 |
合計ジャッジ時間 | 12,878 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct UnionFind{vector< int > data;UnionFind(size_t sz){data.assign(sz, -1);}void unite(int x, int y){x = find(x);y = find(y);if(x != y) {if(data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;}}int find(int k){if(data[k] < 0) return (k);return (data[k] = find(data[k]));}};struct BiConnectedComponents{UnionFind uf;vector< vector< int > > g;vector< pair< int, int > > edges;vector< int > used, ord, low, comp;BiConnectedComponents(size_t v) : uf(v), g(v), used(v, 0), comp(v), ord(v), low(v){}void add_edge(int x, int y){g[x].push_back(y);g[y].push_back(x);edges.push_back(minmax(x, y));}void dfs(int idx, int &k, int par = -1){used[idx] = true;ord[idx] = k++;low[idx] = ord[idx];for(auto &to : g[idx]) {if(!used[to]) {dfs(to, k, idx);low[idx] = min(low[idx], low[to]);if(ord[idx] >= low[to]) uf.unite(idx, to);} else if(to != par) {low[idx] = min(low[idx], ord[to]);}}}int operator[](int k){return (comp[k]);}size_t size(){return (g.size());}void build(vector< vector< int > > &t){int kk = 0;dfs(0, kk);int ptr = 0;vector< int > cc(g.size());for(int i = 0; i < g.size(); i++) {if(i == uf.find(i)) cc[i] = ptr++;}t.resize(ptr);for(int i = 0; i < g.size(); i++) {comp[i] = cc[uf.find(i)];}for(auto &e : edges) {int x = comp[e.first], y = comp[e.second];if(x == y) continue;t[x].push_back(y);t[y].push_back(x);}}};vector< vector< int > > graph;struct CentroidPathDecomposition{struct Centroid{int ParIndex, ParDepth, Deep;vector< int > node;inline int size(){return (node.size());}inline int &operator[](int k){return (node[k]);}inline pair< int, int > Up(){return (make_pair(ParIndex, ParDepth));}};vector< int > SubTreeSize, NextPath;vector< int > TreeIndex, TreeDepth;vector< Centroid > Centroids;void BuildSubTreeSize(){stack< pair< int, int > > s;s.push({0, -1});while(!s.empty()) {auto p = s.top();s.pop();if(~SubTreeSize[p.first]) {NextPath[p.first] = -1;for(auto &to : graph[p.first]) {if(p.second == to) continue;SubTreeSize[p.first] += SubTreeSize[to];if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) {NextPath[p.first] = to;}}} else {s.push(p);SubTreeSize[p.first] = 1;for(auto &to : graph[p.first]) {if(p.second != to) s.push({to, p.first});}}}}void BuildPath(){stack< pair< int, int > > s;Centroids.push_back((Centroid) {-1, -1, 0});s.push({0, -1});TreeIndex[0] = 0;while(!s.empty()) {auto p = s.top();s.pop();TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size();for(auto &to : graph[p.first]) {if(p.second != to) {if(to == NextPath[p.first]) { // Centroid-PathTreeIndex[to] = TreeIndex[p.first];} else { // Not Centroid-PathTreeIndex[to] = Centroids.size();Centroids.push_back((Centroid) {TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1});}s.push({to, p.first});}}Centroids[TreeIndex[p.first]].node.push_back(p.first);}}void Build(){BuildSubTreeSize();BuildPath();}inline int size(){return (Centroids.size());}inline pair< int, int > Information(int idx){return (make_pair(TreeIndex[idx], TreeDepth[idx]));}inline Centroid &operator[](int k){return (Centroids[k]);}inline int LCA(int a, int b) // これを流用する{int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;tie(TreeIdxA, TreeDepthA) = Information(a);tie(TreeIdxB, TreeDepthB) = Information(b);while(TreeIdxA != TreeIdxB) {if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();} else {tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();}}if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);return (Centroids[TreeIdxA][TreeDepthA]);}CentroidPathDecomposition(int SZ){SubTreeSize.assign(SZ, -1);NextPath.resize(SZ);TreeIndex.resize(SZ);TreeDepth.resize(SZ);}int getMax(int a, int b);};struct SegmentTree{vector< int > seg;int sz;SegmentTree(int n){sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz - 1, -1);}int rmq(int a, int b, int k, int l, int r){if(a >= r || b <= l) return (-1);if(a <= l && r <= b) return (seg[k]);return (max(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));}int rmq(int a, int b){return (rmq(a, b, 0, 0, sz));}void update(int k, int x){k += sz - 1;seg[k] = x;while(k > 0) {k = (k - 1) >> 1;seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);}}};vector< SegmentTree > segs;CentroidPathDecomposition *press;void update(int idx, int v){int treeIdx, treeDepth;tie(treeIdx, treeDepth) = press->Information(idx);segs[treeIdx].update(treeDepth, v);}int CentroidPathDecomposition::getMax(int a, int b){int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB, ret = -1;tie(TreeIdxA, TreeDepthA) = Information(a);tie(TreeIdxB, TreeDepthB) = Information(b);while(TreeIdxA != TreeIdxB) {if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {ret = max(ret, segs[TreeIdxA].rmq(0, TreeDepthA + 1));tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();} else {ret = max(ret, segs[TreeIdxB].rmq(0, TreeDepthB + 1));tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();}}if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);ret = max(ret, segs[TreeIdxA].rmq(TreeDepthA, TreeDepthB + 1));return (ret);}int main(){int N, M, Q;cin >> N >> M >> Q;BiConnectedComponents bc(N);for(int i = 0; i < M; i++) {int A, B;cin >> A >> B;bc.add_edge(--A, --B);}bc.build(graph);press = new CentroidPathDecomposition(graph.size());press->Build();for(int i = 0; i < press->size(); i++) {segs.push_back(SegmentTree((*press)[i].size()));}vector< priority_queue< int > > que(graph.size());map< int, int > pos;for(int i = 0; i < Q; i++) {int T, A, B;cin >> T >> A >> B;if(T == 1) {A = bc[--A];assert(pos.count(B) == 0);pos[B] = A;que[A].push(B);if(que[A].top() == B) update(A, que[A].top());} else {int value = press->getMax(bc[--A], bc[--B]);cout << value << endl;if(value >= 1) {int idx = pos[value];que[idx].pop();update(idx, que[idx].empty() ? -1 : que[idx].top());}}}}