結果
問題 | No.529 帰省ラッシュ |
ユーザー | suisen |
提出日時 | 2022-12-11 23:28:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 354 ms / 4,500 ms |
コード長 | 11,007 bytes |
コンパイル時間 | 3,009 ms |
コンパイル使用メモリ | 227,100 KB |
実行使用メモリ | 45,676 KB |
最終ジャッジ日時 | 2024-10-15 18:29:07 |
合計ジャッジ時間 | 9,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 5 ms
5,248 KB |
testcase_05 | AC | 4 ms
5,248 KB |
testcase_06 | AC | 4 ms
5,248 KB |
testcase_07 | AC | 4 ms
5,248 KB |
testcase_08 | AC | 246 ms
22,484 KB |
testcase_09 | AC | 231 ms
22,608 KB |
testcase_10 | AC | 265 ms
29,468 KB |
testcase_11 | AC | 272 ms
29,600 KB |
testcase_12 | AC | 184 ms
21,928 KB |
testcase_13 | AC | 251 ms
45,676 KB |
testcase_14 | AC | 228 ms
27,232 KB |
testcase_15 | AC | 354 ms
33,136 KB |
testcase_16 | AC | 340 ms
33,144 KB |
testcase_17 | AC | 310 ms
42,844 KB |
testcase_18 | AC | 311 ms
43,232 KB |
testcase_19 | AC | 314 ms
40,092 KB |
ソースコード
#line 1 "test/graph/tecc/yuki1290.test.cpp" #define PROBLEM "https://yukicoder.me/problems/1290" #line 2 "src/Template.hpp" #define CUT #include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, l, r) for (int i = (r); i --> (l);) #define all(c) begin(c), end(c) #ifdef LOCAL #define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__) template <class H, class... Ts> void debug_impl(string s, H&& h, Ts&&... ts) { cerr << '(' << s << "): (" << forward<H>(h); ((cerr << ", " << forward<Ts>(ts)), ..., (cerr << ")\n")); } #else #define debug(...) void(0) #endif template <class T> bool chmax(T& a, const T& b) { return b > a ? (a = b, true) : false; } template <class T> bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; } template <class T> istream& operator>>(istream& in, vector<T>& v) { for (auto& e : v) in >> e; return in; } template <class ...Args> void read(Args&... args) { (cin >> ... >> args); } template <class T> ostream& operator<<(ostream& out, const vector<T>& v) { int n = v.size(); rep(i, 0, n) { out << v[i]; if (i + 1 != n) out << ' '; } return out; } template <class H, class ...Ts> void print(H&& h, Ts &&... ts) { cout << h, ((cout << ' ' << forward<Ts>(ts)), ..., (cout << '\n')); } struct io_setup_ { io_setup_() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(10); } } io_setup{}; #undef CUT #define NOTE compile command: \texttt{g++ -std=gnu++17 -Wall -Wextra -g -fsanitize=address -fsanitize=undefined \$\{file\} -o \$\{fileDirname\}/\$\{fileBasenameNoExtension\}} #undef NOTE #define NOTE \texttt{-DLOCAL} を加えると \texttt{debug(...)} による出力が有効となる #undef NOTE #line 3 "src/graph/TECC.hpp" #define CUT #line 2 "src/graph/LowLink.hpp" #line 4 "src/graph/LowLink.hpp" #define CUT struct LowLink { int n, m; vector<pair<int, int>> es; vector<vector<pair<int, int>>> g; vector<int> ord, low, a_ids, b_ids; LowLink(const int n = 0): n(n), m(0), g(n), ord(n, -1), low(n) {} // Returns the id of the added edge int add_edge(int u, int v) { es.emplace_back(u, v); g[u].emplace_back(v, m); g[v].emplace_back(u, m); return m++; } void build() { int t = 0; auto dfs = [&](auto dfs, int u, int id) -> void { bool is_root = id < 0, is_art = false; int cnt = 0; ord[u] = low[u] = t++; for (auto [v, id2] : g[u]) if (id != id2) { if (ord[v] < 0) { ++cnt; dfs(dfs, v, id2); chmin(low[u], low[v]); if (ord[u] <= low[v]) { is_art = not is_root; if (ord[u] != low[v]) b_ids.push_back(id2); } } else { chmin(low[u], ord[v]); } } if (is_art or (is_root and cnt > 1)) { a_ids.push_back(u); } }; rep(i, 0, n) if (ord[i] < 0) dfs(dfs, i, -1); } const pair<int, int>& edge(int edge_id) const { return es[edge_id]; } const vector<pair<int, int>>& edges() const { return es; } // Returns `\{i \mid \text{$e_i$ is a bridge} \}` const vector<int>& bridge_ids() const { return b_ids; } // Returns `\{i \mid \text{$v_i$ is an articulation point} \}` const vector<int>& articulation_points() const { return a_ids; } bool is_bridge(int u, int v) const { if (ord[u] > ord[v]) swap(u, v); return ord[u] < low[v]; } }; #undef CUT #define NOTE buildを忘れない!! #undef NOTE #line 5 "src/graph/TECC.hpp" struct TwoEdgeConnectedComponents: LowLink { // cid[v]: 頂点vが属する二辺連結成分のid vector<int> cid; TwoEdgeConnectedComponents(int n = 0): LowLink(n), cid(n, -1) {} // Returns # of TECCs int build() { LowLink::build(); int num = 0; auto dfs = [&](auto dfs, int u, int p) -> void { cid[u] = p >= 0 and low[u] <= ord[p] ? cid[p] : num++; for (auto [v, _] : g[u]) if (cid[v] < 0) dfs(dfs, v, u); }; rep(i, 0, n) { if (cid[i] < 0) dfs(dfs, i, -1); } return num; } // 先にbuildすること vector<vector<int>> groups() const { const int num = *max_element(all(cid)) + 1; vector<vector<int>> res(num); rep(i, 0, n) res[cid[i]].push_back(i); return res; } // 先にbuildすること // 二重辺連結成分を縮約してできる森を返す。pairは(接続先の二重辺連結成分id, 元の辺id) vector<vector<pair<int, int>>> reduce() const { const int num = *max_element(all(cid)) + 1; vector<vector<pair<int, int>>> res(num); rep(u, 0, n) for (auto [v, eid] : g[u]) { if (int cu = cid[u], cv = cid[v]; cu != cv) { res[cu].emplace_back(cv, eid); } } return res; } }; #undef CUT #define NOTE buildを忘れない!! #undef NOTE #line 3 "src/tree/HLD.hpp" #define CUT struct HLD { int n; vector<int> visit, leave, head, ord, siz, par, dep; private: int dfs(vector<vector<int>>& g, int u, int p) { par[u] = p; int maxsiz = 0; for (int& v : g[u]) if (v != p) { dep[v] = dep[u] + 1; siz[u] += dfs(g, v, u); if (chmax(maxsiz, siz[v])) swap(g[u][0], v); } return siz[u]; } int time = 0; void hld(const vector<vector<int>>& g, int u, int p) { visit[u] = time, ord[time] = u, ++time; head[u] = p >= 0 and g[p][0] == u ? head[p] : u; for (int v : g[u]) if (v != p) hld(g, v, u); leave[u] = time; } public: HLD() = default; HLD(vector<vector<int>>& g, vector<int> roots = {}): n(g.size()), visit(n), leave(n), head(n), ord(n), siz(n, 1), par(n, -1), dep(n) { for (int r : roots) if (par[r] < 0) dfs(g, r, -1); rep(r, 0, n) if (par[r] < 0) dfs(g, r, -1); rep(r, 0, n) if (par[r] < 0) hld(g, r, -1); } int size() const { return n; } int lca(int u, int v) const { for (;; v = par[head[v]]) { if (visit[u] > visit[v]) swap(u, v); if (head[u] == head[v]) return u; } } int la(int u, int k) const { if (k < 0) return -1; while (u >= 0) { int h = head[u]; if (visit[u] - k >= visit[h]) return ord[visit[u] - k]; k -= visit[u] - visit[h] + 1; u = par[h]; } return -1; } int jump(int u, int v, int d) const { if (d < 0) return -1; int w = lca(u, v); int uw = dep[u] - dep[w]; if (d <= uw) return la(u, d); int vw = dep[v] - dep[w]; return d <= uw + vw ? la(v, (uw + vw) - d) : -1; } int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } vector<pair<int, int>> get_path(int u, int v, bool is_edge_query) const { vector<pair<int, int>> res; for (;; v = par[head[v]]) { if (visit[u] > visit[v]) swap(u, v); if (head[u] == head[v]) break; res.emplace_back(visit[head[v]], visit[v] + 1); } res.emplace_back(visit[u] + is_edge_query, visit[v] + 1); return res; } // uvパス上の値を順番通りに掛けた結果を返す template <class T, class Op, class Prod, class RevProd> T fold_path_ordered(int u, int v, Op op, T e, Prod prod, RevProd rev_prod, bool is_edge_query) const { int w = lca(u, v); T sml = e, smr = e; for (auto [l, r] : get_path(u, w, is_edge_query)) sml = op(sml, rev_prod(l, r)); for (auto [l, r] : get_path(v, w, true)) smr = op(prod(l, r), smr); return op(sml, smr); } pair<int, int> get_subtree(int u, bool is_edge_query) const { return { visit[u] + is_edge_query, leave[u] }; } // vertex->id int get_id(int u) const { return visit[u]; } // id->vertexのvector vector<int> inv_ids() const { vector<int> inv(n); rep(i, 0, n) inv[visit[i]] = i; return inv; } vector<int> roots() const { vector<int> res; rep(i, 0, n) if (par[i] < 0) res.push_back(i); return res; } }; #undef CUT #line 3 "src/datastructure/Segtree.hpp" #define CUT template <class S, S(*op)(S, S), S(*e)()> struct Segtree { Segtree(int n = 0): Segtree(vector<S>(n, e())) {} Segtree(const vector<S>& v): _n(v.size()), siz(1 << ceil_log2(_n)), d(2 * siz, e()) { rep(i, 0, _n) d[siz + i] = v[i]; for (int i = siz - 1; i; --i) update(i); } void set(int p, S x) { assert(0 <= p and p < _n); p += siz; d[p] = x; while (p >>= 1) update(p); } S get(int p) const { assert(0 <= p and p < _n); return d[p + siz]; } S prod(int l, int r) const { assert(0 <= l and l <= r and r <= _n); S sml = e(), smr = e(); for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); } return op(sml, smr); } S all_prod() const { return d[1]; } template <class F> int max_right(int l, F f) const { assert(0 <= l and l <= _n); assert(f(e())); if (l == _n) return _n; l += siz; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (not f(op(sm, d[l]))) { while (l < siz) if (l = 2 * l; f(op(sm, d[l]))) sm = op(sm, d[l++]); return l - siz; } sm = op(sm, d[l++]); } while ((l & -l) != l); return _n; } template <class F> int min_left(int r, F f) const { assert(0 <= r and r <= _n); assert(f(e())); if (r == 0) return 0; r += siz; S sm = e(); do { r--; while (r > 1 and r % 2 == 1) r >>= 1; if (not f(op(d[r], sm))) { while (r < siz) if (r = 2 * r + 1; f(op(d[r], sm))) sm = op(d[r--], sm); return r + 1 - siz; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, siz; vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } static int ceil_log2(int n) { int l = 0; while (1 << l < n) ++l; return l; } }; #undef CUT #line 6 "test/graph/tecc/yuki1290.test.cpp" constexpr int inf = numeric_limits<int>::max() / 2; pair<int, int> op(pair<int, int> x, pair<int, int> y) { return max(x, y); } pair<int, int> e() { return { -1, -1 }; } int main() { int n, m, q; read(n, m, q); TwoEdgeConnectedComponents tecc(n); rep(i, 0, m) { int u, v; read(u, v); --u, --v; tecc.add_edge(u, v); } int k = tecc.build(); auto reduced = tecc.reduce(); vector<vector<int>> t(k); rep(i, 0, k) for (auto [j, eid] : reduced[i]) { t[i].push_back(j); } HLD hld(t); vector<priority_queue<int>> pqs(k); Segtree<pair<int, int>, op, e> seg(k); rep(qid, 0, q) { int qt; read(qt); if (qt == 1) { int u, w; read(u, w); --u; u = hld.get_id(tecc.cid[u]); pqs[u].push(w); seg.set(u, { pqs[u].top(), u }); } else { int x, y; read(x, y); --x, --y; x = tecc.cid[x], y = tecc.cid[y]; pair<int, int> res = e(); for (auto [l, r] : hld.get_path(x, y, false)) { res = op(res, seg.prod(l, r)); } print(res.first); if (res.first >= 0) { int u = res.second; pqs[u].pop(); seg.set(u, { pqs[u].size() ? pqs[u].top() : -1 , u }); } } } }