結果

問題 No.529 帰省ラッシュ
ユーザー mugen_1337mugen_1337
提出日時 2020-10-23 21:18:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 539 ms / 4,500 ms
コード長 8,249 bytes
コンパイル時間 3,063 ms
コンパイル使用メモリ 226,296 KB
実行使用メモリ 49,500 KB
最終ジャッジ日時 2023-09-28 15:42:01
合計ジャッジ時間 10,158 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 7 ms
4,376 KB
testcase_05 AC 6 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 6 ms
4,380 KB
testcase_08 AC 350 ms
24,696 KB
testcase_09 AC 341 ms
25,328 KB
testcase_10 AC 399 ms
33,428 KB
testcase_11 AC 394 ms
33,780 KB
testcase_12 AC 316 ms
26,108 KB
testcase_13 AC 254 ms
49,500 KB
testcase_14 AC 356 ms
27,940 KB
testcase_15 AC 539 ms
37,540 KB
testcase_16 AC 531 ms
37,640 KB
testcase_17 AC 474 ms
46,572 KB
testcase_18 AC 467 ms
46,980 KB
testcase_19 AC 469 ms
44,388 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

struct LowLink{
    const vector<vector<int>> &g;
    vector<int> used,ord,low;
    vector<int> articulation;// 関節点
    vector<pair<int,int>> bridge;// 橋
    LowLink(const vector<vector<int>> &g):g(g){}
    int dfs(int pre,int now,int k){
        used[now]=1;
        ord[now]=k++;
        low[now]=ord[now];
        bool is_articulation=false,multi_edge=false;
        int cnt=0;
        for(auto &to:g[now]){
            if(to==pre and !multi_edge){
                multi_edge=true;
                continue;
            }
            if(!used[to]){
                cnt++;
                k=dfs(now,to,k);
                low[now]=min(low[now],low[to]);
                is_articulation|=(pre>=0 and low[to]>=ord[now]);
                if(ord[now]<low[to]) bridge.push_back(minmax(now,to));
            }else{
                // 後退辺
                low[now]=min(low[now],ord[to]);
            }
        }
        // 根の場合子が2個以上いれば関節点
        is_articulation|=(pre==-1 and cnt>1);
        if(is_articulation) articulation.push_back(now);
        return k;
    }
    void build(){
        used.assign(g.size(),0);
        ord.assign(g.size(),0);
        low.assign(g.size(),0);
        int k=0;
        for(int i=0;i<(int)g.size();i++)if(!used[i]) k=dfs(-1,i,k);
    }
    bool isBridge(int u,int v){
        if(ord[u]>ord[v]) swap(u,v);
        return ord[u]<low[v];
    }
};
 
struct TwoEdgeConnectedComponents{
    LowLink LL;
    vector<int> comp;
    vector<vector<int>> tree,group;
 
    TwoEdgeConnectedComponents(const vector<vector<int>> &g):LL(g){}
 
    //点k の属する二重辺連結成分
    int operator[](const int &k){
        return comp[k];
    }
 
    void dfs(int pre,int now,int &k){
        if(pre>=0 and LL.ord[pre]>=LL.low[now]) comp[now]=comp[pre];
        else comp[now]=k++;
        for(auto &to:LL.g[now]){
            if(comp[to]==-1) dfs(now,to,k);
        }
    }
 
    void build(){
        LL.build();
        comp.assign(LL.g.size(),-1);
        int k=0;
        for(int i=0;i<(int)comp.size();i++){
            if(comp[i]==-1) dfs(-1,i,k);
        }
        group.resize(k);
        for(int i=0;i<(int)LL.g.size();i++) group[comp[i]].push_back(i);
        tree.resize(k);
        for(auto &e:LL.bridge){
            int u=comp[e.first],v=comp[e.second];
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
    }
};

struct HLD{
    vector<vector<int>> g;
    // u以下の部分木->[in[u],out[u])
    vector<int> sz,in,out,head,rev,par,dep;
    
    HLD(vector<vector<int>> g):
        g(g),sz(g.size()),in(g.size()),out(g.size()),head(g.size()),rev(g.size()),par(g.size()){}
    
    void build(){
 
        sz.assign(g.size(),0);
        in.assign(g.size(),0);
        out.assign(g.size(),0);
        head.assign(g.size(),0);
        rev.assign(g.size(),0);
        par.assign(g.size(),0);
        dep.assign(g.size(),0);
        dfs_sz(-1,0,0);
        int t=0;
        dfs_hld(-1,0,t);
    }
 
    int la(int v,int k){
        while(true){
            int u=head[v];
            if(in[v]-k>=in[u]) return rev[in[v]-k];
            k-=in[v]-in[u]+1;
            v=par[u];
        }
    }
 
    int lca(int u,int v){
        for(;;v=par[head[v]]){
            /* heavyな辺から先に訪問している
               訪問順が遅い方を上げていけばlcaを超えない*/
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) return u;
        }
    }
 
    int dis(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
 
    /*
    u-v のパスに関するクエリ
    ti: 元的な，ll付けるの忘れない
    q: パスの区間の求値関数，だいたいq(u,v)=seg.query(u,v)
    f: パスごとの結果をマージしていく関数
    */
    template<typename E,typename Q,typename F>
    E query(int u,int v,const E &ti,const Q &q,const F &f,bool edge=false){
        E l=ti,r=ti;
        for(;;v=par[head[v]]){
            if(in[u]>in[v]) swap(u,v),swap(l,r);
            if(head[u]==head[v]) break;
            l=f(q(in[head[v]],in[v]+1),l);
        }
        return f(f(q(in[u]+edge,in[v]+1),l),r);
    }
 
    template<typename Q>
    void add_path(int u,int v,const Q &q,bool edge=false){
        for(;;v=par[head[v]]){
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) break;
            q(in[head[v]],in[v]+1);
        }
        q(in[u]+edge,in[v]+1);
    }
 
    void dfs_sz(int pre,int now,int d){
        dep[now]=d;
        par[now]=pre;
        sz[now]=1;
        if(g[now].size() and g[now][0]==pre) swap(g[now][0],g[now].back());
        for(auto &to:g[now])if(to!=pre){
            dfs_sz(now,to,d+1);
            sz[now]+=sz[to];
            // 0がheavyな辺の先
            if(sz[g[now][0]]<sz[to]) swap(g[now][0],to);
        }
    }
    void dfs_hld(int pre,int now,int &times){
        in[now]=times++;
        rev[in[now]]=now;
        for(auto &to:g[now])if(to!=pre){
            // lightな辺は分割され，headはtoになる
            head[to]=(g[now][0]==to?head[now]:to);
            dfs_hld(now,to,times);
        }
        out[now]=times;
    }
};

template<typename Monoid>
struct SegmentTree{
    using F=function<Monoid(Monoid,Monoid)>;
    int sz;
    vector<Monoid> seg;
    const F f;
    const Monoid gen;
    SegmentTree(int n,const F f,const Monoid &gen):f(f),gen(gen){
        sz=1;
        while(sz<n)sz<<=1;
        seg.assign(2*sz,gen);
    }
    void set(int k,const Monoid &x){
        seg[k+sz]=x;
    }
    void build(){
        for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]);
    }
    void update(int k,const Monoid &x){
        k+=sz;
        seg[k]=x;
        while(k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]);
    }
   // [a,b)
    Monoid query(int a,int b){
        Monoid L=gen,R=gen;
        for(a+=sz,b+=sz;a<b;a>>=1,b>>=1){
            if(a&1) L=f(L,seg[a++]);
            if(b&1) R=f(seg[--b],R);
        }
        return f(L,R);
    }
    Monoid operator[](const int &k)const {
       return seg[k+sz];
    }
};



signed main(){
    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>> g(n);
    rep(i,m){
        int u,v;cin>>u>>v;u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }    

    TwoEdgeConnectedComponents tecc(g);
    tecc.build();

    HLD hld(tecc.tree);
    hld.build();

    SegmentTree<pair<int,int>> seg(n,[&](pair<int,int> lhs,pair<int,int> rhs){return max(lhs,rhs);},make_pair(0,0));
    seg.build();


    vector<priority_queue<int>> ques(n);
    while(q--){
        int t,u,v;cin>>t>>u>>v;u--;
        if(t==1){
            int tid=tecc[u];
            int id=hld.in[tid];
            ques[id].push(v);
            seg.update(id,{ques[id].top(),id});
        }else{
            v--;
            auto res=hld.query(tecc[u],tecc[v],pair<int,int>(0,0),[&](int lw,int hi){return seg.query(lw,hi);},[&](pair<int,int> lhs,pair<int,int> rhs){return max(lhs,rhs);});
            if(res.first==0) cout<<-1<<endl;
            else{
                int id=res.second;
                ques[id].pop();
                if(ques[id].empty()) seg.update(id,{0,id});
                else seg.update(id,{ques[id].top(),id});
                cout<<res.first<<endl;
            }
        }
    }
    return 0;
}
0