結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 ferin
|
| 提出日時 | 2018-08-13 23:43:47 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 711 ms / 4,500 ms |
| コード長 | 8,299 bytes |
| コンパイル時間 | 2,572 ms |
| コンパイル使用メモリ | 199,068 KB |
| 実行使用メモリ | 69,712 KB |
| 最終ジャッジ日時 | 2024-09-24 08:26:11 |
| 合計ジャッジ時間 | 9,962 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 7 ms
6,940 KB |
| testcase_05 | AC | 7 ms
6,940 KB |
| testcase_06 | AC | 7 ms
6,940 KB |
| testcase_07 | AC | 8 ms
6,944 KB |
| testcase_08 | AC | 449 ms
38,356 KB |
| testcase_09 | AC | 458 ms
38,400 KB |
| testcase_10 | AC | 525 ms
45,868 KB |
| testcase_11 | AC | 520 ms
46,744 KB |
| testcase_12 | AC | 395 ms
36,208 KB |
| testcase_13 | AC | 380 ms
69,712 KB |
| testcase_14 | AC | 428 ms
42,688 KB |
| testcase_15 | AC | 687 ms
50,656 KB |
| testcase_16 | AC | 711 ms
50,420 KB |
| testcase_17 | AC | 527 ms
59,900 KB |
| testcase_18 | AC | 526 ms
60,180 KB |
| testcase_19 | AC | 538 ms
57,276 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back
const ll INF = (1LL<<60);
const int MOD = 1000000007;
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.first<<','<<a.second<<')';
return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
out<<'[';
REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
out<<']';
return out;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct HLDecomposition {
int n, pos;
VVI g;
VI vid, // HL分解後のグラフでのid
head, // 頂点が属するheavy-pathのheadのid
sub, // 部分木のサイズ
hvy, // heavy-path上での次の頂点のid
par, // 親のid
depth, // 深さ
inv, // HL分解前のグラフのid（添え字が分解後のid）
type; // 森をHL分解するときの属する木の番号
HLDecomposition(){}
HLDecomposition(int sz):
n(sz), pos(0), g(n),
vid(n,-1), head(n), sub(n,1), hvy(n,-1),
par(n), depth(n), inv(n), type(n) {}
// 辺の追加
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// HL分解の構築を行う
void build(VI rs=VI(1,0)) {
int c=0;
for(int r: rs){
dfs(r);
bfs(r, c++);
}
}
// 根rtからdfsして部分木の大きさ、heavy-edgeの判定などをする
void dfs(int rt) {
stack<PII> st;
par[rt] = -1;
depth[rt] = 0;
st.emplace(rt, 0);
while(!st.empty()) {
int v = st.top().first;
int &i = st.top().second;
if(i < (int)g[v].size()) {
int u = g[v][i++];
if(u == par[v]) continue;
par[u] = v;
depth[u] = depth[v]+1;
st.emplace(u,0);
} else {
st.pop();
int ma = 0;
for(int u: g[v]){
if(u == par[v]) continue;
sub[v] += sub[u];
if(ma < sub[u]) ma = sub[u], hvy[v] = u;
}
}
}
}
// 根r、c番目の木についてchainについての情報をまとめる
void bfs(int r, int c) {
int &k = pos;
queue<int> que;
que.push(r);
while(que.size()) {
int h = que.front(); que.pop();
for(int i=h; i!=-1; i=hvy[i]) {
type[i] = c;
vid[i] = k++;
inv[vid[i]] = i;
head[i] = h;
for(int j: g[i]) {
if(j!=par[i] && j!=hvy[i]) que.push(j);
}
}
}
}
// 頂点に対する処理 [u,v] 開区間なので注意!!!
void for_each(int u, int v, const function<void(int, int)>& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
// [max(vid[head[v]],vid[u]), vid[v]] の区間についての操作を行う
f(max(vid[head[v]], vid[u]), vid[v]);
if(head[u]!=head[v]) v = par[head[v]];
else break;
}
}
// 辺に対する処理 [u,v] 開区間なので注意!!!
void for_each_edge(int u, int v, const function<void(int, int)>& f) {
while(1) {
if(vid[u]>vid[v]) swap(u,v);
if(head[u]!=head[v]) {
f(vid[head[v]], vid[v]);
v = par[head[v]];
} else {
if(u!=v) f(vid[u]+1, vid[v]);
break;
}
}
}
// 頂点u, vのLCA
int lca(int u,int v){
while(1) {
if(vid[u]>vid[v]) swap(u,v);
if(head[u]==head[v]) return u;
v = par[head[v]];
}
}
// 頂点u, vの距離
int distance(int u, int v){
return depth[u] + depth[v] - 2*depth[lca(u,v)];
}
};
struct twoEdgeComponents {
int n;
vector<vector<int>> g; // グラフの隣接リスト
vector<int> cmp; // 頂点iがどの連結成分に属するか
vector<vector<int>> each_bcc; // i番目の連結成分の属する頂点
vector<pair<int,int>> bridge; // i番目の橋
vector<int> order;
vector<bool> inS;
stack<int> roots, S;
twoEdgeComponents() {}
twoEdgeComponents(int n_) : n(n_), g(VVI(n)) {}
twoEdgeComponents(vector<vector<int>> g_) : n(g_.size()), g(g_) {}
void add_edge(int p, int q) {
g[p].push_back(q);
g[q].push_back(p);
}
void dfs(int cur, int prev, int &k) {
order[cur] = ++k;
S.push(cur); inS[cur] = true;
roots.push(cur);
for(auto to: g[cur]) {
if(order[to]==0) dfs(to, cur, k);
else if(to!=prev && inS[to]) {
while(order[roots.top()] > order[to]) roots.pop();
}
}
if(cur == roots.top()) {
if(prev!=-1) bridge.push_back({prev, cur});
vector<int> bcc;
while(1) {
int node = S.top(); S.pop(); inS[node] = false;
bcc.push_back(node);
if(node==cur) break;
}
each_bcc.push_back(bcc);
roots.pop();
}
}
// 二重辺連結成分分解を行う
void bcc() {
order.assign(n, 0);
inS.assign(n, false);
cmp.assign(n, -1);
int k = 0;
for(int i=0; i<n; ++i) {
if(order[i] == 0) {
dfs(i, -1, k);
}
}
for(int i=0; i<(int)each_bcc.size(); ++i) {
for(auto j: each_bcc[i]) {
cmp[j] = i;
}
}
}
// 分解したあとの木を求める
vector<vector<int>> getbcc() {
vector<vector<int>> h(each_bcc.size(), vector<int>());
for(auto i: bridge) {
int a = cmp[i.first], b = cmp[i.second];
h[a].push_back(b);
h[b].push_back(a);
}
return h;
}
};
template <typename monoid>
class segmentTree {
public:
using M = monoid;
using T = typename M::value_type;
int sz;
vector<T> x;
segmentTree(int n = 1e5) {
sz = 1; while(sz < n) sz *= 2;
init();
}
void init() { x.assign(sz*2, M::id()); }
// [a, b)
T query(int a, int b, int k, int l, int r) {
if(r <= a || b <= l) return M::id();
if(a <= l && r <= b) return x[k];
return M::f(query(a, b, 2*k+1, l, (l+r)/2),
query(a, b, 2*k+2, (l+r)/2, r));
}
T query(int a, int b) {return query(a, b, 0, 0, sz);}
// 点更新
void update(int i, const T &val) {
i += sz-1;
x[i] = M::g(x[i], val);
while(i > 0) {
i = (i-1) / 2;
x[i] = M::f(x[i*2+1], x[i*2+2]);
}
}
};
template <typename T>
struct max_monoid {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::min(); }
static T f(const T &a, const T &b) { return max(a, b); }
static T g(const T &a, const T &b) { return b; }
};
template <typename T>
using rmq = segmentTree<max_monoid<T>>;
signed main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int n, m, q;
cin >> n >> m >> q;
VI a(m), b(m);
VVI g(n);
REP(i, m) {
cin >> a[i] >> b[i]; a[i]--, b[i]--;
g[a[i]].PB(b[i]);
g[b[i]].PB(a[i]);
}
twoEdgeComponents bcc(g);
bcc.bcc();
int sz = bcc.bridge.size()+1;
HLDecomposition hld(sz);
for(auto i: bcc.bridge) {
hld.add_edge(bcc.cmp[i.first], bcc.cmp[i.second]);
}
hld.build();
vector<priority_queue<int>> que(sz);
rmq<int> seg(sz);
map<int,int> mp;
REP(i, q) {
int type; cin >> type;
// 追加
if(type == 1) {
int u, w; cin >> u >> w; u--;
int ver = hld.vid[bcc.cmp[u]];
mp[w] = ver;
if(que[ver].empty() || que[ver].top()<w) seg.update(ver, w);
que[ver].push(w);
}
else {
int s, t; cin >> s >> t; s--, t--;
s = bcc.cmp[s], t = bcc.cmp[t];
int ans = -1;
hld.for_each(s, t, [&](int l, int r){
chmax(ans, seg.query(l, r+1));
});
cout << ans << endl;
if(ans == -1) continue;
int ver = mp[ans];
que[ver].pop();
int cost = que[ver].size()?que[ver].top():-1;
seg.update(ver, cost);
}
}
return 0;
}