結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2017-06-10 00:11:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,938 bytes |
コンパイル時間 | 2,305 ms |
コンパイル使用メモリ | 198,624 KB |
実行使用メモリ | 233,624 KB |
最終ジャッジ日時 | 2024-09-22 20:39:57 |
合計ジャッジ時間 | 24,092 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 4 WA * 14 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long long#define MAX_V 114514struct BiconectedGraph{typedef pair<int,int> P;vector<int> G[MAX_V],C[MAX_V],T[MAX_V],ord,low,belong;vector<P> B;int V;bool is_bridge(int u,int v){if(ord[u]>ord[v]) swap(u,v);return ord[u]<low[v];}void dfs(int u,int p,int &k){ord[u]=low[u]=k;++k;for(int v:G[u]){if(v==p) continue;if(ord[v]>=0){low[u]=min(low[u],ord[v]);}else{dfs(v,u,k);low[u]=min(low[u],low[v]);}if(is_bridge(u,v)) B.push_back(P(u,v));}}void fill_component(int c,int u){C[c].push_back(u);belong[u]=c;for(int v:G[u]){if(belong[v]>=0||is_bridge(u,v)) continue;fill_component(c,v);}}void add_component(int u,int &k){if(belong[u]>=0) return;fill_component(k++,u);}void biconnectedgraph(int n){int k=0;ord.clear();ord.resize(n,-1);low.clear();low.resize(n);belong.clear();belong.resize(n,-1);for(int u=0;u<n;u++){if(ord[u]>=0) continue;dfs(u,-1,k);}k=0;for(int i=0;i<(int)B.size();i++){add_component(B[i].first,k);add_component(B[i].second,k);}add_component(0,k);V=k;for(int i=0;i<(int)B.size();i++){int u=belong[B[i].first],v=belong[B[i].second];T[u].push_back(v);T[v].push_back(u);}}};struct HLDecomposition {vector<vector<int>> g;// vid, head, heavy, parent は必須// depth, inv は使用する機能によっては不要vector<int> vid, head, heavy, parent, depth, inv;HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}// 辺 (u, v) を追加するvoid add(int u, int v) {g[u].push_back(v);//g[v].push_back(u);}// 構築するvoid build() {dfs(0, -1);bfs();}int dfs(int curr, int prev) {parent[curr] = prev;int sub = 1, max_sub = 0;for (int next : g[curr]) if (next != prev) {depth[next] = depth[curr] + 1;int sub_next = dfs(next, curr);sub += sub_next;if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;}return sub;}void bfs() {int k = 0;queue<int> q({ 0 });while (!q.empty()) {int h = q.front(); q.pop();for (int i = h; i != -1; i = heavy[i]) {vid[i] = k++;inv[vid[i]] = i;head[i] = h;for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);}}}// 頂点属性の for_eachvoid for_each(int u, int v, function<void(int, int)> f) {if (vid[u] > vid[v]) swap(u, v);f(max(vid[head[v]], vid[u]), vid[v]);if (head[u] != head[v]) for_each(u, parent[head[v]], f);}};struct RMQ{int n;vector<set<int> > dat;RMQ(){}RMQ(int n_){init(n_);}void init(int n_){n=1;while(n<n_) n*=2;dat.clear();dat.resize(2*n-1);}void update(int k,int a){//cout<<k<<" "<<a<<endl;k+=n-1;assert(!dat[k].count(a));dat[k].insert(a);while(k>0){k=(k-1)/2;assert(!dat[k].count(a));dat[k].insert(a);}}void remove(int k,int a){//cout<<k<<" "<<a<<endl;k+=n-1;assert(dat[k].count(a));dat[k].erase(a);while(k>0){k=(k-1)/2;assert(dat[k].count(a));dat[k].erase(a);}}int query(int a,int b,int k,int l,int r){if(r<=a||b<=l) return -1;if(a<=l&&r<=b){if(dat[k].empty()) return -1;return *--dat[k].end();}int vl=query(a,b,k*2+1,l,(l+r)/2);int vr=query(a,b,k*2+2,(l+r)/2,r);return max(vl,vr);}int query(int a,int b){//cout<<a<<" "<<b<<endl;return query(a,b,0,0,n);}};signed main(){ios::sync_with_stdio(0);cin.tie(0);int n,e,q;cin>>n>>e>>q;BiconectedGraph big;for(int i=0;i<e;i++){int s,t;cin>>s>>t;s--;t--;//cout<<s<<" "<<t<<endl;big.G[s].push_back(t);big.G[t].push_back(s);}big.biconnectedgraph(n);int E=0;int V=big.V;HLDecomposition hl(V);for(int i=0;i<V;i++)for(int j:big.T[i]) hl.add(i,j),E++;assert(V==E/2+1);/*//cout<<V<<endl;for(int i=0;i<V;i++)for(int j:big.T[i]) cout<<i<<"->"<<j<<endl;for(int i=0;i<V;i++){cout<<i<<":";for(int j:big.C[i]) cout<<j<<" ";cout<<endl;}//*/hl.build();RMQ rmq(V);map<int,int> m;for(int i=0;i<q;i++){int d;cin>>d;if(d==1){int u,w;cin>>u>>w;u--;u=big.belong[u];//cout<<u<<":"<<w<<endl;m[w]=u;rmq.update(m[w],w);}if(d==2){int s,t;cin>>s>>t;s--;t--;s=big.belong[s];t=big.belong[t];int ans=-1;hl.for_each(s, t, [&](int l, int r) {ans = max(ans,rmq.query(l, r + 1));//cout<<ans<<endl;});cout<<ans<<endl;if(~ans) rmq.remove(m[ans],ans);}}return 0;}