結果
問題 | No.529 帰省ラッシュ |
ユーザー | raven7959 |
提出日時 | 2022-09-02 10:55:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,008 bytes |
コンパイル時間 | 3,678 ms |
コンパイル使用メモリ | 242,580 KB |
実行使用メモリ | 40,584 KB |
最終ジャッジ日時 | 2024-04-27 13:56:12 |
合計ジャッジ時間 | 9,039 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 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 | 168 ms
19,736 KB |
testcase_13 | AC | 240 ms
40,584 KB |
testcase_14 | AC | 274 ms
27,520 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 306 ms
38,588 KB |
testcase_18 | AC | 278 ms
38,852 KB |
testcase_19 | WA | - |
ソースコード
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2") #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n" #define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n" using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vs = vector<string>; using vc = vector<char>; using vd = vector<double>; using vld = vector<long double>; using vvi = vector<vector<int>>; using vvl = vector<vector<ll>>; using vvs = vector<vector<string>>; using vvc = vector<vector<char>>; using vvd = vector<vector<double>>; using vvld = vector<vector<long double>>; using vvvi = vector<vector<vector<int>>>; using vvvl = vector<vector<vector<ll>>>; using vvvvi = vector<vector<vector<vector<int>>>>; using vvvvl = vector<vector<vector<vector<ll>>>>; using pii = pair<int,int>; using pll = pair<ll,ll>; const int INF = 1e9; const ll LINF = 2e18; template <class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } bool ispow2(int i) { return i && (i & -i) == i; } bool ispow2(ll i) { return i && (i & -i) == i; } template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template <typename T> istream& operator>>(istream& is, vector<T>& v) { for (int i = 0; i < int(v.size()); i++) { is >> v[i]; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < int(v.size()); i++) { os << v[i]; if (i < int(v.size()) - 1) os << ' '; } return os; } static uint32_t RandXor(){ static uint32_t x=123456789; static uint32_t y=362436069; static uint32_t z=521288629; static uint32_t w=88675123; uint32_t t; t=x^(x<<11); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } static long double Rand01(){ return (RandXor()+0.5)*(1.0/UINT_MAX); } template <typename T = int> struct Edge{ int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template <typename T = int> struct Graph{ vector<vector<Edge<T>>> g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const{ return g.size(); } void add_directed_edge(int from, int to, T cost = 1){ g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1){ g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false){ for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if (weighted) cin >> c; if (directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector<Edge<T>> &operator[](const int &k){ return g[k]; } inline const vector<Edge<T>> &operator[](const int &k) const{ return g[k]; } }; template <typename T = int> using Edges = vector<Edge<T>>; template<typename T> vector<int> bridge_tree_decomposition(Graph<T> &G){ int N=(int)G.g.size(); vector<bool> visited(N); vector<int> ord(N),low(N),cmp(N,-1); int ts=0,idx=0; auto dfs=[&](auto &&self,int v,int p=-1)->void{ visited[v]=true; ord[v]=ts; low[v]=ord[v]; ts++; bool flg=false; for(auto nv:G[v]){ if(!visited[nv]){ self(self,nv,v); low[v]=min(low[v],low[nv]); } else if(nv!=p){ low[v]=min(low[v],ord[nv]); } else{ if(!flg) flg=true; else low[v]=min(low[v],ord[p]); } } }; auto dfs2=[&](auto &&self,int v)->void{ for(auto nv:G[v]){ if(cmp[nv]!=-1) continue; if(low[nv]<=ord[v]) cmp[nv]=cmp[v]; else{ cmp[nv]=idx; idx++; } self(self,nv); } }; for(int i=0;i<N;i++) if(!visited[i]) dfs(dfs,i); for(int i=0;i<N;i++){ if(cmp[i]==-1){ cmp[i]=idx; idx++; dfs2(dfs2,i); } } return cmp; } // HeavyLightDecomposition<Graph<int>> HLD(g,root); などする,rootは指定しない場合0になる // size: 部分木のサイズ(元の木の頂点番号->サイズ) // depth: 深さ(元の木の頂点番号->深さ) // down: 行きがけ順(セグ木上での順番でもある) (元の木の頂点番号->行きがけ順) // up: 部分木クエリに使うやつ // nxt: ある頂点が属する連結成分の中で最も浅い頂点(元の木の頂点番号->元の木の頂点番号) // par: 親の番号(元の木の頂点番号->元の木の頂点番号) // rev: 行きがけ順から元の木の頂点番号に戻す配列 // void path_query(int u,int v,bool vertex,F f): u,vパスについての可換なクエリを処理,頂点属性ならvertexをtrueにする // void path_noncommutative_query(int u,int v,bool vertex,F f): u,vパスについての非可換なクエリを処理,頂点属性ならvertexをtrueにする // void subtree_query(int u,bool vertex,F f): uを根とする部分木についてのクエリを処理 // 上3つではいずれもラムダ式でfを渡せばよく,[l,r)についての結果をどこかにまとめる感じで書くと良い // その他,汎用的な関数がある(lca,la,dist,in_subtree,move) template <typename G> struct HeavyLightDecomposition{ private: void dfs_sz(int cur){ size[cur] = 1; for (auto &dst : g[cur]){ if (dst == par[cur]){ if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]); else continue; } depth[dst] = depth[cur] + 1; par[dst] = cur; dfs_sz(dst); size[cur] += size[dst]; if (size[dst] > size[g[cur][0]]) swap(dst, g[cur][0]); } } void dfs_hld(int cur){ down[cur] = id++; rev[down[cur]] = cur; for (auto dst : g[cur]){ if (dst == par[cur]) continue; nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst)); dfs_hld(dst); } up[cur] = id; } // [u, v) vector<pair<int, int>> ascend(int u, int v) const{ if(u == v) return {}; vector<pair<int, int>> res; while (nxt[u] != nxt[v]){ res.emplace_back(down[u], down[nxt[u]]); u = par[nxt[u]]; } if (u != v) res.emplace_back(down[u], down[v] + 1); return res; } // (u, v] vector<pair<int, int>> descend(int u, int v) const{ if (u == v) return {}; if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}}; auto res = descend(u, par[nxt[v]]); res.emplace_back(down[nxt[v]], down[v]); return res; } public: G &g; int id; vector<int> size, depth, down, up, nxt, par, rev; HeavyLightDecomposition(G &_g, int root = 0) : g(_g), id(0), size(g.size(), 0), depth(g.size(), 0), down(g.size(), -1), up(g.size(), -1), nxt(g.size(), root), par(g.size(), root), rev(g.size(), root) { dfs_sz(root); dfs_hld(root); } void build(int root){ dfs_sz(root); dfs_hld(root); } pair<int, int> idx(int i) const { return make_pair(down[i], up[i]); } template <typename F> void path_query(int u, int v, bool vertex, const F &f){ int l = lca(u, v); for (auto &&[a, b] : ascend(u, l)){ int s = a + 1, t = b; s > t ? f(t, s) : f(s, t); } if (vertex) f(down[l], down[l] + 1); for (auto &&[a, b] : descend(l, v)){ int s = a, t = b + 1; s > t ? f(t, s) : f(s, t); } } template <typename F> void path_noncommutative_query(int u, int v, bool vertex, const F &f){ int l = lca(u, v); for (auto &&[a, b] : ascend(u, l)) f(a + 1, b); if (vertex) f(down[l], down[l] + 1); for (auto &&[a, b] : descend(l, v)) f(a, b + 1); } template <typename F> void subtree_query(int u, bool vertex, const F &f){ f(down[u] + int(!vertex), up[u]); } int lca(int a, int b){ while (nxt[a] != nxt[b]){ if (down[a] < down[b]) swap(a, b); a = par[nxt[a]]; } return depth[a] < depth[b] ? a : b; } int lca(int r, int u, int v){ return lca(r, u) ^ lca(u, v) ^ lca(v, r); } int la(int v, int k) { while(1){ int u = nxt[v]; if(down[v] - k >= down[u]) return rev[down[v] - k]; k -= down[v] - down[u] + 1; v = par[nxt[u]]; } } int dist(int a, int b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; } // bがaの部分木内にあるか bool in_subtree(int a, int b) { return down[a] <= down[b] && down[b] <= up[a]; } // aからbの方向に1進んだ頂点を返す int move(int a, int b) { assert(a != b); if(in_subtree(b,a)){ return par[a]; } else{ if(lca(a,b)==a){ return la(b,dist(a,b)-1); } else{ return par[a]; } } } // s-tパス上にxがあるか bool in_path(int s, int t, int x){ return dist(s, x) + dist(x, t) == dist(s, t); } }; int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } struct segtree{ public: segtree() : segtree(0) {} segtree(int n) : _n(n) { log = ceil_pow2(_n); size = 1 << log; pq=vector<priority_queue<int>>(size); d=vector<pii>(2*size); rep(i,_n) d[size+i].second=i; rep(i,size) add(i,-1); } void add(int p,int x){ pq[p].emplace(x); d[p+size].first=pq[p].top(); p+=size; for (int i = 1; i <= log; i++){ int x=p>>i; if(d[2*x].first>=d[2*x+1].first) d[x]=d[2*x]; else d[x]=d[2*x+1]; } } void erase(int p){ pq[p].pop(); d[p+size].first=pq[p].top(); p+=size; for (int i = 1; i <= log; i++){ int x=p>>i; if(d[2*x].first>=d[2*x+1].first) d[x]=d[2*x]; else d[x]=d[2*x+1]; } } pii prod(int l, int r){ assert(0 <= l && l <= r && r <= _n); pii ret(-1,-1); l += size; r += size; while (l < r){ if (l & 1){ if(ret.first<d[l].first) ret=d[l]; l++; } if (r & 1){ r--; if(ret.first<d[r].first) ret=d[r]; } l >>= 1; r >>= 1; } return ret; } private: int _n, size, log; vector<priority_queue<int>> pq; vector<pii> d; }; void solve(){ int N,M,Q; cin>>N>>M>>Q; vi A(M),B(M); Graph<int> original_graph(N); rep(i,M){ cin>>A[i]>>B[i]; A[i]--; B[i]--; original_graph.add_edge(A[i],B[i]); } auto ret=bridge_tree_decomposition(original_graph); int X=*max_element(all(ret))+1; Graph<int> G(X); rep(i,M){ if(ret[A[i]]!=ret[B[i]]){ G.add_edge(ret[A[i]],ret[B[i]]); } } HeavyLightDecomposition<Graph<int>> HLD(G,0); segtree seg(X); while(Q--){ int t; cin>>t; if(t==1){ int u,w; cin>>u>>w; u--; seg.add(ret[u],w); } else{ int s,t; cin>>s>>t; s--; t--; s=ret[s]; t=ret[t]; pii tmp(-1,-1); auto f=[&](int l,int r)->void{ auto x=seg.prod(l,r); if(x.first>tmp.first) tmp=x; }; HLD.path_query(s,t,true,f); cout<<tmp.first<<"\n"; if(tmp.first!=-1) seg.erase(tmp.second); } } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }