結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 mamekin
|
| 提出日時 | 2018-03-18 20:44:10 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 801 ms / 4,500 ms |
| コード長 | 10,822 bytes |
| コンパイル時間 | 2,711 ms |
| コンパイル使用メモリ | 150,160 KB |
| 実行使用メモリ | 46,492 KB |
| 最終ジャッジ日時 | 2024-12-29 22:44:42 |
| 合計ジャッジ時間 | 13,377 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;
void bridgeDecomposition(
const vector<vector<int> >& edges, vector<int>& indexConvert,
vector<vector<int> >& nodesOut)
{
const int n = edges.size();
vector<int> num(n, -1), low(n, -1);
vector<bool> isStk(n, false);
stack<int> stk;
int cnt = -1;
nodesOut.clear();
for(int i=0; i<n; ++i){
stack<tuple<int, int, unsigned> > arg;
arg.push(make_tuple(i, -1, 0));
while(!arg.empty()){
int v = get<0>(arg.top());
int prev = get<1>(arg.top());
unsigned j = get<2>(arg.top());
arg.pop();
if(j == 0){
if(num[v] != -1)
continue;
num[v] = low[v] = ++ cnt;
stk.push(v);
isStk[v] = true;
}
else{
int w = edges[v][j-1];
if(w != prev && isStk[w])
low[v] = min(low[v], low[w]);
}
if(j < edges[v].size()){
arg.push(make_tuple(v, prev, j + 1));
int w = edges[v][j];
if(w != prev)
arg.push(make_tuple(w, v, 0));
}
else if(low[v] == num[v]){
nodesOut.push_back(vector<int>());
for(;;){
int w = stk.top();
stk.pop();
isStk[w] = false;
nodesOut.back().push_back(w);
if(v == w)
break;
}
}
}
}
const int m = nodesOut.size();
indexConvert.resize(n);
for(int i=0; i<m; ++i){
for(unsigned j=0; j<nodesOut[i].size(); ++j)
indexConvert[nodesOut[i][j]] = i;
}
}
void bridgeDecomposition(
const vector<vector<int> >& edges, vector<int>& indexConvert,
vector<vector<int> >& nodesOut, vector<vector<int> >& edgesOut)
{
bridgeDecomposition(edges, indexConvert, nodesOut);
const int n = edges.size();
const int m = nodesOut.size();
edgesOut.assign(m, vector<int>());
vector<set<int> > used(m);
for(int i=0; i<n; ++i){
for(unsigned j=0; j<edges[i].size(); ++j){
int v = indexConvert[i];
int w = indexConvert[edges[i][j]];
if(v != w && used[v].find(w) == used[v].end()){
edgesOut[v].push_back(w);
used[v].insert(w);
}
}
}
}
class SegmentTree
{
public:
typedef pair<int, int> T1;
typedef pair<int, int> T2;
// データの初期値、以下の条件を満たすこと
// uniteData(v, INIT_DATA) == v
static const T1 INIT_DATA;
// 2つの区間の計算結果v1,v2に対して、
// その2つの区間を統合した区間における計算結果を返す
static T1 uniteData(T1 v1, T1 v2){
return max(v1, v2);
}
private:
// 前回の値がprevである要素に対して、
// パラメータxを用いた更新処理を適用した後の計算結果を返す
T1 updateData(T1 prev, T2 x){
if(x == INIT_DATA)
return prev;
else
return x;
}
int n;
vector<T1> data;
void updateTree(int a, int k, int l, int r, T2 x){
if(a == l && a == r){
data[k] = updateData(data[k], x);
}
else if(l <= a && a <= r){
updateTree(a, k*2+1, l, (l+r)/2, x);
updateTree(a, k*2+2, (l+r+1)/2, r, x);
data[k] = uniteData(data[k*2+1], data[k*2+2]);
}
}
T1 getValue(int a, int b, int k, int l, int r){
if(a <= l && r <= b){
return data[k];
}
else if(a <= r && l <= b){
T1 v1 = getValue(a, b, k*2+1, l, (l+r)/2);
T1 v2 = getValue(a, b, k*2+2, (l+r+1)/2, r);
return uniteData(v1, v2);
}
else{
return INIT_DATA;
}
}
public:
SegmentTree(int n0){
n = 1;
while(n < n0)
n *= 2;
data.assign(2*n-1, INIT_DATA);
}
SegmentTree(const vector<T1>& v) : SegmentTree((int)v.size()){
for(unsigned i=0; i<v.size(); ++i)
data[n-1+i] = v[i];
for(int k=n-2; k>=0; --k)
data[k] = uniteData(data[k*2+1], data[k*2+2]);
}
// a番目の要素にパラメータxによる更新処理を適用
void update(int a, T2 x){
updateTree(a, 0, 0, n-1, x);
}
// 区間[a,b]の計算結果を返す
T1 get(int a, int b){
return getValue(a, b, 0, 0, n-1);
}
};
const SegmentTree::T1 SegmentTree::INIT_DATA(-1, -1);
class HeavyLightDecomposition
{
private:
typedef SegmentTree DataStructure;
typedef DataStructure::T1 T1;
typedef DataStructure::T2 T2;
static const T1 INIT_DATA;
// 長さnの配列に対するデータ構造を生成
DataStructure makeDataStructure(int n){
return DataStructure(n);
}
// 初期値initの配列に対するデータ構造を生成
DataStructure makeDataStructure(const vector<T1>& init){
return DataStructure(init);
}
// データ構造の更新処理
void updateDataStructure(DataStructure& ds, int a, T2 x){
ds.update(a, x);
}
void updateDataStructure(DataStructure& ds, int a, int b, T2 x){
}
// データ構造のデータ取得
T1 getValFromDataStructure(DataStructure& ds, int a, int b, T1 prev){
return DataStructure::uniteData(ds.get(a, b), prev);
}
vector<DataStructure> dsList;
vector<int> depth;
vector<int> parent;
vector<vector<int> > node;
vector<pair<int, int> > index;
// 深さ優先探索によりHL分解を実行
pair<int, int> dfs(const vector<vector<int> >& edges, int curr, int prev)
{
if(prev != -1){
depth[curr] = depth[prev] + 1;
parent[curr] = prev;
}
int sum = 1;
pair<int, int> p(-1, -1);
for(int next : edges[curr]){
if(next == prev)
continue;
pair<int, int> p2 = dfs(edges, next, curr);
sum += p2.first;
p = max(p, p2);
}
if(p.first == -1){
p.second = node.size();
node.resize(p.second + 1);
}
node[p.second].push_back(curr);
return make_pair(sum, p.second);
}
public:
// コンストラクタ
HeavyLightDecomposition(const vector<vector<int> >& edges, int root)
{
int n = edges.size();
depth.assign(n, 0);
parent.assign(n, -1);
dfs(edges, root, -1);
index.resize(n);
for(unsigned i=0; i<node.size(); ++i){
for(unsigned j=0; j<node[i].size(); ++j)
index[node[i][j]] = make_pair(i, j);
dsList.push_back(makeDataStructure(node[i].size()));
}
}
// コンストラクタ（初期値あり）
HeavyLightDecomposition(const vector<vector<int> >& edges, int root, const vector<T1>& init)
{
int n = edges.size();
depth.assign(n, 0);
parent.assign(n, -1);
dfs(edges, root, -1);
index.resize(n);
for(unsigned i=0; i<node.size(); ++i){
vector<T1> v(node[i].size());
for(unsigned j=0; j<node[i].size(); ++j){
index[node[i][j]] = make_pair(i, j);
v[j] = init[node[i][j]];
}
dsList.push_back(makeDataStructure(v));
}
}
// ノードaに対して、パラメータxによる更新を適用
void update(int a, T2 x){
updateDataStructure(dsList[index[a].first], index[a].second, x);
}
// a,b間のパスに対して、パラメータxによる更新を適用
void update(int a, int b, T2 x){
while(index[a].first != index[b].first){
int a2 = node[index[a].first].back();
int b2 = node[index[b].first].back();
if(depth[a2] < depth[b2]){
swap(a, b);
swap(a2, b2);
}
updateDataStructure(dsList[index[a].first], index[a].second, index[a2].second, x);
a = parent[a2];
}
if(depth[a] < depth[b])
swap(a, b);
updateDataStructure(dsList[index[a].first], index[a].second, index[b].second, x);
}
// a,b間のパスの結果を取得
T1 get(int a, int b){
T1 ans = INIT_DATA;
while(index[a].first != index[b].first){
int a2 = node[index[a].first].back();
int b2 = node[index[b].first].back();
if(depth[a2] < depth[b2]){
swap(a, b);
swap(a2, b2);
}
ans = getValFromDataStructure(dsList[index[a].first], index[a].second, index[a2].second, ans);
a = parent[a2];
}
if(depth[a] < depth[b])
swap(a, b);
return getValFromDataStructure(dsList[index[a].first], index[a].second, index[b].second, ans);
}
};
const HeavyLightDecomposition::T1 HeavyLightDecomposition::INIT_DATA = SegmentTree::INIT_DATA;
int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<vector<int> > edges0(n);
for(int i=0; i<m; ++i){
int a, b;
cin >> a >> b;
-- a;
-- b;
edges0[a].push_back(b);
edges0[b].push_back(a);
}
vector<int> indexConvert;
vector<vector<int> > nodes;
vector<vector<int> > edges;
bridgeDecomposition(edges0, indexConvert, nodes, edges);
vector<priority_queue<int> > pq(edges.size());
HeavyLightDecomposition hl(edges, 0);
while(--q >= 0){
int type, a, b;
cin >> type >> a >> b;
if(type == 1){
int i = indexConvert[a-1];
if(pq[i].empty() || pq[i].top() < b)
hl.update(i, make_pair(b, i));
pq[i].push(b);
}
else{
int i = indexConvert[a-1];
int j = indexConvert[b-1];
pair<int, int> p = hl.get(i, j);
cout << p.first << endl;
if(p.first != -1){
int k = p.second;
pq[k].pop();
if(pq[k].empty())
hl.update(k, make_pair(-1, k));
else
hl.update(k, make_pair(pq[k].top(), k));
}
}
}
return 0;
}