結果
問題 |
No.529 帰省ラッシュ
|
ユーザー |
![]() |
提出日時 | 2025-01-14 20:21:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 345 ms / 4,500 ms |
コード長 | 12,632 bytes |
コンパイル時間 | 6,785 ms |
コンパイル使用メモリ | 340,000 KB |
実行使用メモリ | 63,932 KB |
最終ジャッジ日時 | 2025-01-14 20:21:41 |
合計ジャッジ時間 | 11,383 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#ifdef t9unkubj #include"debug.cpp" //#include"template_no_debug.h" #else #define dbg(...) 199958 #endif #undef _GLIBCXX_DEBUG #pragma GCC optimize("O3") using namespace std; #include<bits/stdc++.h> using ll=long long; using ull=unsigned long long; template<class T>using vc=vector<T>; template<class T>using vvc=vc<vc<T>>; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() template<class T,class F> bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template<class T, class F> bool chmax(T &x, F y){ if(x<y){ x=y; return true; } return false; } double pass_time=0; using S=pair<int,int>; S e(){ return {-1e9,-1}; } /* https://atcoder.jp/contests/arc039/tasks/arc039_d https://kntychance.hatenablog.jp/entry/2022/09/16/161858 */ struct Edge{ int from; int to; int id; }; struct graph{ vector<vector<Edge>>g; vector<int>low,ord; vector<int>ea,eb; vector<int>used; int n; graph(int n):n(n),g(n),low(n),ord(n){} int edge_num=0; void add_edge(int a,int b,int is_both=1){ g[a].push_back({a,b,edge_num}); if(is_both)g[b].push_back({b,a,edge_num}); ea.push_back(a); eb.push_back(b); used.push_back(0); edge_num++; } struct cycle_scanner{ vector<int>seen,finish; vector<Edge>hist; int n; vector<vector<Edge>>g; cycle_scanner(vector<vector<Edge>>g):g(g),n(g.size()){ } int dfs(int now,const Edge&pre,int can_rev){ seen[now]=1; hist.push_back(pre); for(auto&e:g[now]){ if(can_rev==0&&pre.id==e.id)continue; if(finish[e.to]){ continue; } if(seen[e.to]&&!finish[e.to]){ hist.push_back(e); return e.to; } int res=dfs(e.to,e,can_rev); if(res!=-1)return res; } finish[now]=1; hist.pop_back(); return -1; } vector<Edge>constructer(int pos){ vector<Edge>res; while(hist.size()){ auto p=hist.back();hist.pop_back(); res.push_back(p); if(p.from==pos)break; } reverse(res.begin(), res.end()); return res; } //有向グラフなら1,そうでないなら0を与える vector<Edge>find_v(int can_rev){ seen.resize(n),finish.resize(n); int pos=-1; for(int i=0;i<n;i++){ if(seen[i])continue; pos=dfs(i,{-1,-1,-1},can_rev); if(pos!=-1){ return constructer(pos); } } return {}; } }; //有向グラフなら1,そうでないなら0を与える vector<Edge> cycle_scan(int can_rev){ cycle_scanner cyc(g); return cyc.find_v(can_rev); } int lowlinked=0; void lowlink(){ if(lowlinked)return; lowlinked=1; vector<int>seen(n); auto dfs=[&](auto&dfs,int u,int v,int&now)->int{ seen[u]=1; ord[u]=now++; low[u]=ord[u]; for(auto [from,x,i]:g[u]){ if(i==v)continue; if(seen[x]){ low[u]=min(low[u],ord[x]); }else{ used[i]=1; low[u]=min(low[u],dfs(dfs,x,i,now)); } } return low[u]; }; int now=0; for(int i=0;i<n;i++){ if(!seen[i]){ dfs(dfs,i,-1,now); } } } vector<int>two_comp_num; vector<vector<int>>two_comp; void make_two_comp(){ if(two_comp.size())return; lowlink(); two_comp_num=vector<int>(n); vector<vector<int>>res; dfs1(0,-1,res); for(int i=0;i<int(res.size());i++){ for(auto x:res[i]){ two_comp_num[x]=i; } } two_comp=res; } void dfs2(int u,int v,vector<int>&vs); int is_bridge(int i){ if(!used[i])return 0; int a1=ea[i],a2=eb[i]; if(ord[a1]>ord[a2])swap(a1,a2); if(ord[a1]>=low[a2])return 0; return 1; } void dfs1(int u,int v,vector<vector<int>>&res){ vector<int>vs{u}; for(auto [_,x,i]:g[u]){ if(x==v)continue; if(!used[i])continue; if(!is_bridge(i)){ dfs2(x,u,res,vs); }else{ dfs1(x,u,res); } } res.push_back(vs); } void dfs2(int u,int v,vector<vector<int>>&res,vector<int>&vs){ vs.push_back(u); for(auto [_,x,i]:g[u]){ if(x==v)continue; if(!used[i])continue; if(!is_bridge(i)){ dfs2(x,u,res,vs); }else{ dfs1(x,u,res); } } } vector<vector<int>>two_g;//二重辺連結成分分解して成分ごとに縮約した気 void make_two_g(){ make_two_comp(); auto res=two_comp; two_g.resize(res.size()); for(int i=0;i<(int)ea.size();i++){ if(two_comp_num[ea[i]]!=two_comp_num[eb[i]]){ two_g[two_comp_num[ea[i]]].push_back(two_comp_num[eb[i]]); two_g[two_comp_num[eb[i]]].push_back(two_comp_num[ea[i]]); } } } //https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_A vector<int>is_art; void make_art(){ lowlink(); is_art.resize(n); int res=0; for(auto [_,x,i]:g[0]){ if(used[i])res++; } is_art[0]=res>=2; for(int i=1;i<n;i++){ for(auto [_,x,idx]:g[i]){ if(used[idx]&&ord[i]<=low[x])is_art[i]=1; } } } //なんもわかんねーなにこれ //https://ei1333.github.io/luzhiled/snippets/graph/bi-connected-components.html //https://judge.yosupo.jp/submission/226252 vector<vector<pair<int,int>>> bc;//おなじ連結成分に属している辺 vector<vector<int>>bcs;//頂点 void bic(){ lowlink(); vector<int>used(n); vector<pair<int,int>>tmp; auto dfs=[&](auto&dfs,int u,int v)->void{ used[u]=1; for(auto [_,x,idx]:g[u]){ if(x==v)continue; if(!used[x]||ord[x]<ord[u]){ tmp.push_back(minmax(x,u)); } if(!used[x]){ dfs(dfs,x,u); if(low[x]>=ord[u]){ bc.push_back(vector<pair<int,int>>()); while(1){ auto p=tmp.back();tmp.pop_back(); bc.back().push_back(p); if(p.first==min(x,u)&&p.second==max(x,u)){ break; } } } } } if(g[u].size()==0){//孤立点 bcs.push_back(vector<int>{u}); } }; for(int i=0;i<n;i++){ if(!used[i])dfs(dfs,i,-1); } vector<int>added(n); for(auto x:bc){ bcs.push_back(vector<int>()); for(auto [a,b]:x){ auto add=[&](int x){ if(added[x])return; bcs.back().push_back(x); added[x]=1; }; add(a),add(b); } for(auto x:bcs.back())added[x]=0; } } }; #include<vector> #include<cassert> #include<algorithm> struct HLD{ int n; std::vector<int>depth,head,siz_,par,in,out; std::vector<std::vector<int>>g,c; HLD(int n):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(n),c(n){} HLD(int n,std::vector<std::vector<int>>g):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(g),c(n){} int inited=0; void add_edge(int u,int v,bool d=0){ g[u].emplace_back(v); if(d)g[v].emplace_back(u); } void init_dfs1(int now,int pre){ for(int &x:g[now]){ if(x==pre)continue; c[now].emplace_back(x); depth[x]=depth[now]+1; par[x]=now; init_dfs1(x,now); siz_[now]+=siz_[x]; } } void init_dfs2(int now,int pre,int&order){ in[now]=order++; for(int i=0;i<(int)c[now].size();i++){ if(siz_[c[now][0]]<siz_[c[now][i]])std::swap(c[now][0],c[now][i]); } for(int x:c[now]){ if(x==c[now][0])head[x]=head[now]; else head[x]=x; init_dfs2(x,now,order); } out[now]=order++; } void init(int root=0){//rootからの有向辺にになることに注意 par=head=std::vector<int>(n,root); int order{}; init_dfs1(root,-1); init_dfs2(root,-1,order); } int lca(int u,int v){//O(logN) u,vのlcaを取得する if(head[u]==head[v])return (depth[u]>depth[v]?v:u); if(depth[head[u]]>depth[head[v]])std::swap(u,v); v=par[head[v]]; return lca(u,v); } int f1(int a){//入った時間を返すO(1) return in[a]; } int f2(int a){//出た時間を返すO(1) return out[a]; } int dis(int u,int v){//uとvの最短距離を求めるO(logN) assert(0<=u&&u<n); assert(0<=v&&v<n); return depth[u]+depth[v]-2*depth[lca(u,v)]; } template<class T,class G> void set(int u,T&seg,G x){ seg.set(f1(u),x); } S prod(int u,int v,bool edge,auto&seg){//[u,v]の演算結果を取得する,G>ret T>seg木 O(log^2N) S res=e(); while(1){ if(in[u]>in[v])swap(u,v); if(head[u]==head[v])break; chmax(res,seg.prod(in[head[v]],in[v]+1)); v=par[head[v]]; } return max(res,seg.prod(in[u]+edge,in[v]+1)); } vector<vector<int>>db; void la_init(){ int log=0; while((1<<log)<n)log++; db.resize(log,vector<int>(n)); db[0]=par; for(int i=1;i<log;i++){ for(int j=0;j<n;j++){ int nxt=db[i-1][j]; if(nxt==-1)db[i][j]=-1; else{ db[i][j]=db[i-1][nxt]; } } } } int la(int x,int p){ int now=0; while(p){ if(p&1)x=db[now][x]; p>>=1; now++; if(x==-1)return -1; } return x; } }; struct segtree{ vc<S>node; int n; segtree(int n):n(n),node(n*2,e()){} void set(int i,S x){ node[i+=n]=x; while(i>>=1)node[i]=max(node[i*2],node[i*2+1]); } S prod(int l,int r){ l+=n,r+=n; S res=e(); while(l<r){ if(l&1)chmax(res,node[l++]); if(r&1)chmax(res,node[--r]); l/=2; r/=2; } return res; } }; void solve(){ int n,m,q; cin>>n>>m>>q; graph g(n); rep(i,m){ int a,b; cin>>a>>b; g.add_edge(--a,--b); } g.make_two_g(); auto G=g.two_g; int N=G.size(); HLD hld(N); rep(i,N)for(auto&x:G[i])hld.add_edge(i,x); hld.init(); segtree seg(N*2); vc<priority_queue<int>>que(N); while(q--){ int f,s,t; cin>>f>>s>>t; if(f==1){ --s; s=g.two_comp_num[s]; que[s].push(t); if(que[s].top()==t)seg.set(hld.f1(s),{t,s}); }else{ --s,--t; s=g.two_comp_num[s]; t=g.two_comp_num[t]; auto R=hld.prod(s,t,0,seg); dbg(R); if(R.second>=0){ que[R.second].pop(); seg.set(hld.f1(R.second),e()); if(que[R.second].size()){ seg.set( hld.f1(R.second), {que[R.second].top(),R.second}); } cout<<R.first<<"\n"; }else cout<<"-1\n"; } } } signed main(){ cin.tie(0)->sync_with_stdio(0); pass_time=clock(); int t=1; //cin>>t; while(t--)solve(); pass_time=clock()-pass_time; dbg(pass_time/CLOCKS_PER_SEC); }