結果

問題 No.529 帰省ラッシュ
ユーザー blackyukiblackyuki
提出日時 2021-03-14 16:43:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 668 ms / 4,500 ms
コード長 4,827 bytes
コンパイル時間 2,555 ms
コンパイル使用メモリ 220,116 KB
最終ジャッジ日時 2025-01-19 17:05:19
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define rosrt(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
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 outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];};cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outp(T p){cout<<'('<<p.fi<<','<<p.se<<')'<<endl;}
template<class T> void outvp(T v){for(auto x:v)cout<<'('<<x.fi<<','<<x.se<<')';cout<<endl;}
#define PQ(a) priority_queue<a>
class segtree{
    ll N=1;
    P g=P(-1,-1);
    vector<PQ(ll)> v;
    vp seg;
    P f(P a,P b){return max(a,b);}
public:
    segtree(ll n){
        while(N<n)N*=2;
        seg=vp(N*2-1,g);
        rep(i,n)seg[i+N-1].se=i;
        v=vector<PQ(ll)>(n);
    }
    void add(ll i,ll x){
        v[i].push(x);
        seg[i+N-1].fi=v[i].top();
        i+=N-1;
        while(i>0){
            i=(i-1)/2;
            seg[i]=f(seg[i*2+1],seg[i*2+2]);
        }
    }
    void er(ll i){
        v[i].pop();
        if(v[i].size())seg[i+N-1].fi=v[i].top();
        else seg[i+N-1].fi=-1;
        i+=N-1;
        while(i>0){
            i=(i-1)/2;
            seg[i]=f(seg[i*2+1],seg[i*2+2]);
        }
    }
    P get(ll a,ll b){
        P res=P(-1,-1);
        a+=N-1;b+=N-1;
        while(a<b){
            if(!(a&1))chmax(res,seg[a]);
            if(!(b&1))chmax(res,seg[b-1]);
            a=a>>1;b=(b-1)>>1;
        }
        return res;
    }
};
int main(){
    ll n,m,q;cin>>n>>m>>q;
    vvp g(n);
    rep(i,m){
        ll a,b;cin>>a>>b;
        a--;b--;
        g[a].pb(b,i);g[b].pb(a,i);
    }
    vi lk(n),dep(n,-1);
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        lk[i]=dep[i];
        for(auto x:g[i])if(x.fi!=p){
            if(dep[x.fi]==-1){
                dep[x.fi]=dep[i]+1;
                dfs(x.fi,i);
                chmin(lk[i],lk[x.fi]);
            }
            else{
                chmin(lk[i],dep[x.fi]);
            }
        }
    };dep[0]=0;dfs(0,-1);
    vb is_bridge(m,false);
    function<void(ll,ll)> dfs2=[&](ll i,ll e){
        if(e!=-1&&lk[i]==dep[i])is_bridge[e]=true;
        for(auto x:g[i])if(dep[x.fi]==dep[i]+1)dfs2(x.fi,x.se);
    };dfs2(0,-1);
    ll cmp=0;
    vi gr(n,-1);
    function<void(ll)> dfs3=[&](ll i){
        for(auto x:g[i])if(!is_bridge[x.se]&&gr[x.fi]==-1){
            gr[x.fi]=gr[i];dfs3(x.fi);
        }
    };rep(i,n)if(gr[i]==-1){gr[i]=cmp++;dfs3(i);}
    vvi tree(cmp);
    rep(i,n)for(auto x:g[i])if(is_bridge[x.se]){
        tree[gr[i]].pb(gr[x.fi]);
    }
    n=cmp;
    vvi G=tree;
    vi sub(n);
    function<void(ll,ll)> initHLD=[&](ll i,ll p){
        sub[i]=1;
        ll ma=0;
        rep(j,G[i].size())if(G[i][j]!=p){
            initHLD(G[i][j],i);
            sub[i]+=sub[G[i][j]];
            if(chmax(ma,sub[G[i][j]]))swap(G[i][j],G[i][0]);
        }
    };initHLD(0,-1);
    vi head(n),par(n);
    function<void(ll,ll)> initHLD2=[&](ll i,ll p){
        par[i]=p;
        rep(j,G[i].size())if(G[i][j]!=p){
            if(j==0)head[G[i][j]]=head[i];
            else head[G[i][j]]=G[i][j];
            initHLD2(G[i][j],i);
        }
    };head[0]=0;initHLD2(0,-1);
    vi euler(n);
    ll c=0;
    function<void(ll)> tour=[&](ll i){
        euler[i]=c++;
        for(ll x:G[i])if(x!=par[i])tour(x);
    };tour(0);
    auto lca=[&](ll a,ll b){
        while(head[a]!=head[b]){
            if(dep[head[a]]<dep[head[b]])swap(a,b);
            a=par[head[a]];
        }
        if(dep[a]>dep[b])return b;
        return a;
    };
    P res;
    segtree seg(n);
    auto do_path=[&](ll a,ll b){
        while(head[a]!=head[b]){
            if(dep[head[a]]<dep[head[b]])swap(a,b);
            chmax(res,seg.get(euler[head[a]],euler[a]+1));
            a=par[head[a]];
        }
        chmax(res,seg.get(min(euler[a],euler[b]),max(euler[a],euler[b])+1));
    };
    // outv(euler);
    rep(i,q){
        ll t;cin>>t;
        if(t==1){
            ll a,b;cin>>a>>b;
            a=gr[a-1];
            seg.add(euler[a],b);
        }
        else{
            ll a,b;cin>>a>>b;
            res=P(-1,-1);
            do_path(gr[a-1],gr[b-1]);
            out(res.fi);
            if(res.fi!=-1)seg.er(res.se);
        }
    }
}
0