結果
問題 | No.529 帰省ラッシュ |
ユーザー | blackyuki |
提出日時 | 2021-01-24 14:37:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 6,269 bytes |
コンパイル時間 | 3,056 ms |
コンパイル使用メモリ | 233,584 KB |
実行使用メモリ | 45,952 KB |
最終ジャッジ日時 | 2024-06-10 21:24:57 |
合計ジャッジ時間 | 14,456 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | RE | - |
testcase_04 | AC | 11 ms
5,376 KB |
testcase_05 | AC | 10 ms
5,376 KB |
testcase_06 | AC | 10 ms
5,376 KB |
testcase_07 | AC | 11 ms
5,376 KB |
testcase_08 | AC | 712 ms
28,520 KB |
testcase_09 | AC | 631 ms
26,880 KB |
testcase_10 | AC | 675 ms
30,736 KB |
testcase_11 | AC | 705 ms
30,976 KB |
testcase_12 | AC | 478 ms
24,832 KB |
testcase_13 | AC | 423 ms
45,952 KB |
testcase_14 | RE | - |
testcase_15 | AC | 919 ms
33,024 KB |
testcase_16 | AC | 908 ms
32,896 KB |
testcase_17 | AC | 636 ms
42,240 KB |
testcase_18 | AC | 640 ms
42,880 KB |
testcase_19 | AC | 653 ms
39,808 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define all(a) a.begin(),a.end() #define rsort(a) {sort(all(a));reverse(all(a));} #define pb emplace_back #define eb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue<T> #define SPQ(T) priority_queue<T,vector<T>,greater<T>> #define dame(a) {out(a);return 0;} #define decimal cout<<fixed<<setprecision(15); #define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());} typedef long long ll; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> PP; typedef tuple<ll,ll,ll,ll> PPP; typedef multiset<ll> S; using vi=vector<ll>; using vvi=vector<vi>; using vvvi=vector<vvi>; using vvvvi=vector<vvvi>; using vp=vector<P>; using vvp=vector<vp>; using vpp=vector<PP>; using vb=vector<bool>; using vvb=vector<vb>; using vvvb=vector<vvb>; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;} template<class T> void out(T a){cout<<a<<'\n';} template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';} template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';} template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';} template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);} template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template<class T> void yesno(T b){if(b)out("yes");else out("no");} template<class T> void YesNo(T b){if(b)out("Yes");else out("No");} template<class T> void YESNO(T b){if(b)out("YES");else out("NO");} template<class T> void noyes(T b){if(b)out("no");else out("yes");} template<class T> void NoYes(T b){if(b)out("No");else out("Yes");} template<class T> void NOYES(T b){if(b)out("NO");else out("YES");} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} P ans; class segtree{ vp seg;ll N=1; vector<priority_queue<ll>> pq; public: segtree(ll n){ pq=vector<priority_queue<ll>>(n); while(N<n)N*=2; seg=vp(N*2-1,P(-1,-1)); } void update(ll i,ll x){ seg[i+N-1]=P(x,i); i+=N-1; while(i>0){ i=(i-1)/2; seg[i]=max(seg[i*2+1],seg[i*2+2]); } } P ma(ll a,ll b,ll k,ll l,ll r){ if(a<=l&&r<=b)return seg[k]; if(r<=a||b<=l)return P(-1,-1); return max(ma(a,b,k*2+1,l,(l+r)/2),ma(a,b,k*2+2,(l+r)/2,r)); } void query(ll a,ll b){ chmax(ans,ma(a,b,0,0,N)); // outp(P(a,b)); } void erase(ll i){ pq[i].pop();if(pq[i].empty())pq[i].push(-1); update(i,pq[i].top()); } void add(ll i,ll x){ pq[i].push(x); update(i,pq[i].top()); } }; class UF{ vi data;stack<P> st; public: UF(ll n){ data=vi(n,1); } bool merge(ll x,ll y,bool undo=false){ x=root(x);y=root(y); if(data[x]>data[y])swap(x,y); if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);} if(x==y)return false; data[y]+=data[x];data[x]=-y; return true; } ll root(ll i){if(data[i]>0)return i;return root(-data[i]);} ll getsize(ll i){return data[root(i)];} bool same(ll a,ll b){return root(a)==root(b);} void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}} }; int main(){ ll n,m,q;cin>>n>>m>>q; vvp g(n);vp edge(m);UF uf(n); rep(i,m){ ll a,b;cin>>a>>b;a--;b--; g[a].pb(b,i);g[b].pb(a,i); edge[i]=P(a,b); } vb bridge(m,false); vi dep(n,-1); function<ll(ll,ll,ll,ll)> lk=[&](ll i,ll e,ll p,ll d){ dep[i]=d; ll res=n+100; for(auto x:g[i])if(x.se!=e){ if(dep[x.fi]!=-1)chmin(res,dep[x.fi]); else chmin(res,lk(x.fi,x.se,i,d+1)); } if(res>=dep[i]&&e!=-1)bridge[e]=true; else if(e!=-1)uf.merge(i,p); return res; }; vi root; rep(i,n)if(dep[i]==-1){ lk(i,-1,-1,0); root.pb(i); } vi num(n,-1);ll c=0; function<void(ll)> makenum=[&](ll i){ if(uf.root(i)==i)num[i]=c++; for(auto x:g[i])if(dep[x.fi]==dep[i]+1)makenum(x.fi); }; for(ll r:root)makenum(r); vvi tree(c); rep(i,m)if(bridge[i]){ ll a=num[uf.root(edge[i].fi)],b=num[uf.root(edge[i].se)]; tree[a].pb(b);tree[b].pb(a); } vi par(c),head(c),id(c),sz(c,1); ll cnt=0; function<void(ll,ll)> init=[&](ll i,ll p){ par[i]=p; P ma=P(0,0); rep(j,tree[i].size())if(tree[i][j]!=p){ init(tree[i][j],i); sz[i]+=sz[tree[i][j]]; chmax(ma,P(sz[tree[i][j]],j)); } swap(tree[i][0],tree[i][ma.se]); }; init(0,-1); function<void(ll,ll)> HLD=[&](ll i,ll p){ id[i]=cnt++; rep(j,tree[i].size())if(tree[i][j]!=p){ if(j)head[tree[i][j]]=tree[i][j]; else head[tree[i][j]]=head[i]; HLD(tree[i][j],i); } }; HLD(0,-1); segtree seg(c); function<void(ll,ll)> query=[&](ll a,ll b){ ll A=head[a],B=head[b]; if(A==B)seg.query(min(id[a],id[b]),max(id[a],id[b])+1); else if(id[A]<id[B]){ seg.query(id[B],id[b]+1); query(a,par[B]); } else{ seg.query(id[A],id[a]+1); query(par[A],b); } }; rep(qq,q){ ll md;cin>>md; if(md==2){ ans=P(-1,-1); ll x,y;cin>>x>>y;x--;y--;x=num[uf.root(x)];y=num[uf.root(y)]; query(x,y); out(ans.fi); if(ans.se!=-1)seg.erase(ans.se); } else{ ll i,a;cin>>i>>a;i--;i=num[uf.root(i)]; seg.add(id[i],a); } } }