結果
問題 | No.529 帰省ラッシュ |
ユーザー | nanophoto12 |
提出日時 | 2021-05-05 21:11:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,636 bytes |
コンパイル時間 | 5,475 ms |
コンパイル使用メモリ | 293,052 KB |
実行使用メモリ | 58,864 KB |
最終ジャッジ日時 | 2024-09-13 14:05:15 |
合計ジャッジ時間 | 13,440 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 446 ms
20,936 KB |
testcase_13 | AC | 595 ms
58,864 KB |
testcase_14 | AC | 501 ms
23,680 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 501 ms
36,964 KB |
testcase_18 | AC | 505 ms
37,436 KB |
testcase_19 | WA | - |
ソースコード
#include <bits/stdc++.h> #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) #include <bits/stdc++.h> using namespace std; template<typename T> void chmax(T& reference, T value) { reference = max(reference, value); } template<typename T> void chmaxmap(map<T, T>& m, T key, T value) { if (m.count(key)) { chmax(m[key], value); } else { m[key] = value; } } template<typename T> void chmin(T& reference, T value) { reference = min(reference, value); } #include <atcoder/all> using namespace atcoder; typedef modint1000000007 mint; template< typename G > struct HeavyLightDecomposition { G& g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G& g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for (auto& to : g[idx]) { if (to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int& times) { in[idx] = times++; rev[in[idx]] = idx; for (auto& to : g[idx]) { if (to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while (1) { int u = head[v]; if (in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) { T l = ti, r = ti; for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v), swap(l, r); if (head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); } template< typename Q > void add(int u, int v, const Q& q, bool edge = false) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; typedef vector<vector<int>> UnWeightedGraph; class lca { public: typedef vector<vector<int>> Graph; const int n; const int log2_n; std::vector<std::vector<int>> parent; std::vector<int> depth; lca(const Graph& g, int root) : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) { dfs(g, root, -1, 0); for (int k = 0; k + 1 < log2_n; k++) { for (int v = 0; v < (int)g.size(); v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void dfs(const Graph& g, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int j = 0; j < g[v].size(); j++) { if (g[v][j] != p) dfs(g, g[v][j], v, d + 1); } } int get(int u, int v) { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < log2_n; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = log2_n - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[get(u, v)]; } }; namespace { using namespace std; template< typename G > struct LowLink { const G& g; vector< int > used, ord, low; vector< int > articulation; vector< pair< int, int > > bridge; LowLink(const G& g) : g(g) {} int dfs(int idx, int k, int par) { used[idx] = true; ord[idx] = k++; low[idx] = ord[idx]; bool is_articulation = false; int cnt = 0; for (auto& to : g[idx]) { if (!used[to]) { ++cnt; k = dfs(to, k, idx); low[idx] = min(low[idx], low[to]); is_articulation |= ~par && low[to] >= ord[idx]; if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int)to)); } else if (to != par) { low[idx] = min(low[idx], ord[to]); } } is_articulation |= par == -1 && cnt > 1; if (is_articulation) articulation.push_back(idx); return k; } virtual void build() { used.assign(g.size(), 0); ord.assign(g.size(), 0); low.assign(g.size(), 0); int k = 0; for (int i = 0; i < g.size(); i++) { if (!used[i]) k = dfs(i, k, -1); } } }; template< typename G > struct TwoEdgeConnectedComponents { vector< int > comp; LowLink< G > lowLink_; TwoEdgeConnectedComponents(const G& g) : lowLink_(g) {} int operator[](const int& k) { return comp[k]; } void dfs(int idx, int par, int& k) { if (~par && lowLink_.ord[par] >= lowLink_.low[idx]) comp[idx] = comp[par]; else comp[idx] = k++; for (auto& to : lowLink_.g[idx]) { if (comp[to] == -1) dfs(to, idx, k); } } typedef std::vector<std::vector<int>> UnWeightedGraph; void build(UnWeightedGraph& t) { lowLink_.build(); comp.assign(lowLink_.g.size(), -1); int k = 0; for (int i = 0; i < comp.size(); i++) { if (comp[i] == -1) dfs(i, -1, k); } t.resize(k); for (auto& e : lowLink_.bridge) { int x = comp[e.first], y = comp[e.second]; t[x].push_back(y); t[y].push_back(x); } } }; } ll op(ll left, ll right) { return max(left, right); } ll e() { return -1; } int main() { int n, m, q; cin >> n >> m >> q; vector<vector<int>> g(n); rep(i, m) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } typedef vector<vector<int>> G; TwoEdgeConnectedComponents<G> comp(g); G links; comp.build(links); HeavyLightDecomposition<G> hld(links); hld.build(); vector<set<ll>> monstors(links.size()); segtree<ll, op, e> all(links.size()); rep(i, links.size()) all.set(i, -1); map<ll, int> vToId; vector<ll> ans; rep(_, q) { ll args, u, v; cin >> args >> u >> v; if (args == 1) { u--; int id = comp.comp[u]; monstors[id].insert(v); vToId[v] = id; if (all.get(id) < v) { all.set(id, v); } } else { u--; v--; int id1 = comp.comp[u]; int id2 = comp.comp[v]; ll t = hld.query(id1, id2, -1LL, [&](int x, int y) { return all.prod(x, y); }, [&](ll x, ll y) { return max(x, y); }); ans.push_back(t); if (t != -1) { int id = vToId[t]; monstors[id].erase(t); vToId.erase(t); if (monstors[id].size()) { all.set(id, *monstors[id].rbegin()); } else { all.set(id, -1); } } } } for (auto x : ans) { cout << x << endl; } return 0; }