結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 Forested
|
| 提出日時 | 2020-11-19 18:13:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 275 ms / 4,500 ms |
| コード長 | 10,652 bytes |
| コンパイル時間 | 2,335 ms |
| コンパイル使用メモリ | 215,688 KB |
| 最終ジャッジ日時 | 2025-01-16 01:42:27 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
// Template
#include "bits/stdc++.h"
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T>
inline bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
struct IOSET {
IOSET() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
}
} ioset;
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
for (T &element : vec) is >> element;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) {
os << vec[i] << (i + 1 == vec_len ? "" : " ");
}
return os;
}
// Two Edge Connected Components
#include <vector>
#include <stack>
template <typename G>
class TwoEdgeConnectedComponents {
const G &g;
std::stack<int> st0, st1;
std::vector<int> order;
int t;
void dfs(int v, int p) {
order[v] = t++;
st0.push(v);
st1.push(v);
bool pcnt = false;
for (int u : g[v]) {
if (order[u] == -1) {
dfs(u, v);
} else {
if (u == p && !pcnt) {
pcnt = true;
continue;
}
while (order[st1.top()] > order[u]) {
st1.pop();
}
}
}
if (st1.top() == v) {
while (true) {
int x = st0.top();
st0.pop();
comp[x] = k;
if (x == v) {
break;
}
}
++k;
st1.pop();
}
}
public:
std::vector<int> comp;
int k;
TwoEdgeConnectedComponents(const G &_g) : g(_g) {
build();
}
void build() {
int sz = g.size();
order.assign(sz, -1);
comp.assign(sz, -1);
t = 0;
k = 0;
for (int i = 0; i < sz; ++i) {
if (order[i] == -1) {
dfs(i, -1);
}
}
}
};
// Graph
#include <vector>
#include <iostream>
template <typename E>
class Graph {
std::vector<std::vector<E>> g;
public:
Graph() : g(0) {}
Graph(int n) : g(n) {}
Graph(int n, int m) : g(n) {
while (m--) {
int v;
E e;
std::cin >> v >> e;
add_edge(v, e);
}
}
int size() const {
return (int)g.size();
}
void add_edge(int from, const E &edge) {
g[from].push_back(edge);
}
const std::vector<E> &operator[](int v) const {
return g[v];
}
std::vector<E> &operator[](int v) {
return g[v];
}
};
template <typename T>
struct Wedge {
int to;
T cost;
Wedge(int _to, T _cost) : to(_to), cost(_cost) {}
operator int() const {
return to;
}
};
template <typename T>
std::istream &operator>>(std::istream &is, Wedge<T> &e) {
is >> e.to >> e.cost;
return is;
}
// Heavy-Light Decomposition
#include <vector>
#include <utility>
template <typename G>
struct HeavyLightDecomposition {
G &g;
std::vector<int> sz, par, head, in, rin;
HeavyLightDecomposition(G &_g) : g(_g) {
build();
}
void build() {
sz.assign(g.size(), 0);
par.assign(g.size(), 0);
dfs_size(0, -1);
head.assign(g.size(), 0);
in.assign(g.size(), 0);
rin.assign(g.size(), 0);
int t = 0;
dfs_hld(0, -1, t);
}
int lca(int u, int v) {
while (true) {
if (in[u] > in[v]) {
std::swap(u, v);
}
if (head[u] == head[v]) {
return u;
}
v = par[head[v]];
}
}
template <typename T, typename F0, typename F1>
T query(int u, int v, const T &identity, const F0 &f0, const F1 &f1, bool edge) {
T _u = identity, _v = identity;
while (true) {
if (in[u] > in[v]) {
std::swap(u, v);
std::swap(_u, _v);
}
if (head[u] == head[v]) {
break;
}
_v = f1(f0(in[head[v]], in[v] + 1), _v);
v = par[head[v]];
}
return f1(f1(f0(in[u] + edge, in[v] + 1), _v), _u);
}
template <typename F>
void update(int u, int v, const F &f, bool edge) {
while (true) {
if (in[u] > in[v]) {
std::swap(u, v);
}
if (head[u] == head[v]) {
break;
}
f(in[head[v]], in[v] + 1);
v = par[head[v]];
}
f(in[u] + edge, in[v] + 1);
}
private:
void dfs_size(int v, int p) {
par[v] = p;
sz[v] = 1;
int l = g[v].size();
if (l && (int)g[v][0] == p) std::swap(g[v][0], g[v][l - 1]);
for (int i = 0; i < l; ++i) {
if ((int)g[v][i] == p) {
continue;
}
dfs_size((int)g[v][i], v);
sz[v] += sz[(int)g[v][i]];
if (sz[(int)g[v][i]] > sz[(int)g[v][0]]) {
std::swap(g[v][0], g[v][i]);
}
}
}
void dfs_hld(int v, int p, int &t) {
in[v] = t++;
rin[in[v]] = v;
int l = g[v].size();
for (int i = 0; i < l; ++i) {
if ((int)g[v][i] == p) {
continue;
}
head[(int)g[v][i]] = (i ? (int)g[v][i] : head[v]);
dfs_hld((int)g[v][i], v, t);
}
}
};
// Segment Tree
#include <vector>
#include <cassert>
template <typename Operator>
struct SegmentTree {
using NodeType = decltype(Operator::identity());
int length, n_;
std::vector<NodeType> node;
SegmentTree(int n) {
assert(n >= 0);
n_ = n;
length = 1;
while (length < n) length <<= 1;
node.assign(length << 1, Operator::identity());
}
SegmentTree(int n, NodeType x) {
assert(n >= 0);
n_ = n;
length = 1;
while (length < n) length <<= 1;
node.assign(length << 1, x);
for (int i = length - 1; i > 0; --i) node[i] = Operator::func(node[(i << 1) | 0], node[(i << 1) | 1]);
}
SegmentTree(std::vector<NodeType> &vec) : n_((int)vec.size()) {
length = 1;
while (length < (int)vec.size()) length <<= 1;
node.assign(2 * length, Operator::identity());
for (int i = 0; i < (int)vec.size(); ++i) node[i + length] = vec[i];
for (int i = length - 1; i > 0; --i) node[i] = Operator::func(node[(i << 1) | 0], node[(i << 1) | 1]);
}
void update(int idx, NodeType val) {
assert(idx >= 0 && idx < n_);
idx += length;
node[idx] = val;
while (idx >>= 1) node[idx] = Operator::func(node[(idx << 1) | 0], node[(idx << 1) | 1]);
}
NodeType get(int l, int r) {
assert(l >= 0 && l <= n_ && r >= 0 && r <= n_ && l <= r);
l += length;
r += length;
NodeType vl = Operator::identity(), vr = Operator::identity();
while (r > l) {
if (l & 1) vl = Operator::func(vl, node[l++]);
if (r & 1) vr = Operator::func(node[--r], vr);
l >>= 1;
r >>= 1;
}
return Operator::func(vl, vr);
}
template <typename F>
int max_right(int l, F f) {
assert(l >= 0 && l < n_);
l += length;
NodeType sum = Operator::identity();
do {
while (!(l & 1)) l >>= 1;
if (!f(Operator::func(sum, node[l]))) {
while (l < length) {
l <<= 1;
if (f(Operator::func(sum, node[l]))) {
sum = Operator::func(sum, node[l]);
++l;
}
}
return l - length;
}
sum = Operator::func(sum, node[l]);
++l;
} while ((l & -l) != l);
return n_;
}
};
// Main
struct RMQ {
using NodeType = pair<int, int>;
static NodeType identity() {
return pair<int, int>(0, 0);
}
static NodeType func(NodeType x, NodeType y) {
return max(x, y);
}
};
int main() {
int n, m, q;
cin >> n >> m >> q;
Graph<int> g(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a;
--b;
g.add_edge(a, b);
g.add_edge(b, a);
}
TwoEdgeConnectedComponents<Graph<int>> c(g);
Graph<int> tree(c.k);
rep(i, n) for (int j : g[i]) {
if (c.comp[i] != c.comp[j]) tree.add_edge(c.comp[i], c.comp[j]);
}
HeavyLightDecomposition<Graph<int>> hld(tree);
SegmentTree<RMQ> seg(c.k);
vector<priority_queue<int>> pq(c.k);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int u, w;
cin >> u >> w;
--u;
u = c.comp[u];
int old = 0;
if (!pq[u].empty()) old = pq[u].top();
pq[u].push(w);
if (w > old) {
seg.update(hld.in[u], pair<int, int>(w, u));
}
} else {
int s, t;
cin >> s >> t;
--s;
--t;
s = c.comp[s];
t = c.comp[t];
auto f0 = [&](int x, int y) -> RMQ::NodeType {
return seg.get(x, y);
};
auto f1 = [&](RMQ::NodeType x, RMQ::NodeType y) -> RMQ::NodeType {
return RMQ::func(x, y);
};
RMQ::NodeType p = hld.query(s, t, RMQ::identity(), f0, f1, false);
if (p.first == 0) {
cout << "-1\n";
} else {
cout << p.first << "\n";
pq[p.second].pop();
seg.update(hld.in[p.second], pair<int, int>((pq[p.second].empty() ? 0 : pq[p.second].top()), p.second));
}
}
}
}