#1035335 (C++23) No.529 帰省ラッシュ

提出ソース
結果

問題	No.529 帰省ラッシュ
コンテスト
ユーザー	t9unkubj
提出日時	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
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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);
}
yukicoder

結果

ソースコード
