結果

問題 No.529 帰省ラッシュ
コンテスト
ユーザー Chanyuh
提出日時 2020-05-04 16:09:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 638 ms / 4,500 ms
コード長 7,876 bytes
コンパイル時間 2,187 ms
コンパイル使用メモリ 132,072 KB
実行使用メモリ 52,740 KB
最終ジャッジ日時 2024-06-24 12:20:55
合計ジャッジ時間 10,626 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

class HLD {
private:
  void dfs_sz(int v) {
    for(int &u:G[v])
      if(u==par[v]) swap(u,G[v].back());
    if(~par[v]) G[v].pop_back();

    for(int &u:G[v]){
      par[u]=v;
      dep[u]=dep[v]+1;
      dfs_sz(u);
      sub[v]+=sub[u];
      if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]);
    }
  }

  void dfs_hld(int v,int c,int &pos) {
    vid[v]=pos++;
    inv[vid[v]]=v;
    type[v]=c;
    for(int u:G[v]){
      if(u==par[v]) continue;
      head[u]=(u==G[v][0]?head[v]:u);
      dfs_hld(u,c,pos);
    }
  }

public:
  vector< vector<int> > G;
  vector<int> vid, head, sub, par, dep, inv, type;

  HLD(int n):
    G(n),vid(n,-1),head(n),sub(n,1),
    par(n,-1),dep(n,0),inv(n),type(n){}

  void add_edge(int u,int v) {
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void build(vector<int> rs={0}) {
    int c=0,pos=0;
    for(int r:rs){
      dfs_sz(r);
      head[r]=r;
      dfs_hld(r,c++,pos);
    }
  }

  int lca(int u,int v){
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]==head[v]) return u;
      v=par[head[v]];
    }
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
  }

  // for_each(vertex)
  // [l, r) <- attention!!
  template<typename F>
  void for_each(int u, int v, const F& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      f(max(vid[head[v]],vid[u]),vid[v]+1);
      if(head[u]!=head[v]) v=par[head[v]];
      else break;
    }
  }

  template<typename T,typename Q,typename F>
  T for_each(int u,int v,T ti,const Q &q,const F &f){
    T l=ti,r=ti;
    while(1){
      if(vid[u]>vid[v]){
        swap(u,v);
        swap(l,r);
      }
      l=f(l,q(max(vid[head[v]],vid[u]),vid[v]+1));
      if(head[u]!=head[v]) v=par[head[v]];
      else break;
    }
    return f(l,r);
  }

  // for_each(edge)
  // [l, r) <- attention!!
  template<typename F>
  void for_each_edge(int u, int v,const F& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]!=head[v]){
        f(vid[head[v]],vid[v]+1);
        v=par[head[v]];
      }else{
        if(u!=v) f(vid[u]+1,vid[v]+1);
        break;
      }
    }
  }
};



template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;//二項演算
  T ti;//単位元
  vector<T> dat;

  SegmentTree(){}
  SegmentTree(F f,T ti):f(f),ti(ti){}

  void init(int n_){//sizeがn_のsegtreeを作る
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }

  void build(const vector<T> &v){//vによってsegtreeをbuildする
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  void set_val(int k,T x){//k番目をxにする
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(int a,int b){//区間[a,b)に対しFを適応した値を返す
    if(a>=b) return ti;
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){//
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }

  T &operator [] (int i) {return dat[i+n];};
};


struct TwoEdgeConnectedComponents{
  vector<int> ord,low,par,blg,sz;
  vector<vector<int>> G,C;

  TwoEdgeConnectedComponents(int n):
    ord(n,-1),low(n),par(n,-1),blg(n,-1),sz(n,1),G(n){}

  void add_edge(int u,int v){
    if(u==v) return;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  bool is_bridge(int u,int v){
    if(ord[u]>ord[v]) swap(u,v);
    return ord[u]<low[v];
  }

  void dfs(int v,int &pos){
    ord[v]=low[v]=pos++;
    int dup=0;
    for(int u:G[v]){
      if(u==par[v] and !dup){
        dup=1;
        continue;
      }
      if(~ord[u]){
        low[v]=min(low[v],ord[u]);
        continue;
      }
      par[u]=v;
      dfs(u,pos);
      sz[v]+=sz[u];
      low[v]=min(low[v],low[u]);
    }
  }

  void fill_component(int v){
    C[blg[v]].emplace_back(v);
    for(int u:G[v]){
      if(~blg[u]||is_bridge(u,v)) continue;
      blg[u]=blg[v];
      fill_component(u);
    }
  }

  void add_component(int v,int &k){
    if(~blg[v]) return;
    blg[v]=k++;
    C.emplace_back();
    fill_component(v);
  }

  int build(){
    int n=G.size(),pos=0;
    for(int i=0;i<n;i++)
      if(ord[i]<0) dfs(i,pos);

    int k=0;
    for(int i=0;i<n;i++) add_component(i,k);

    return k;
  }

  const vector<int>& operator[](int i)const{return C[i];}

  vector<vector<int>> forest(){
    int n=G.size(),k=C.size();
    vector<vector<int>> T(k);
    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          T[blg[v]].emplace_back(blg[u]);
    return T;
  }
};

int n,m,q;
int V;
int cmp[100010];
map<int,int> W;
priority_queue<int> que[100010];

void solve(){
  cin >> n >> m >> q;
  TwoEdgeConnectedComponents tecc(n);
  rep(i,m){
    int a,b;cin >> a >> b;a--;b--;
    tecc.add_edge(a,b);
  }
  tecc.build();
  vector<vector<int>> G=tecc.forest();
  V=G.size();
  rep(i,V){
    for(int t:tecc[i]){
      cmp[t]=i;
    }
  }
  // rep(i,n){
  //   cout << cmp[i] << " ";
  // }
  // cout << "" << endl;
  HLD hld(V);
  rep(i,V){
    for(int t:G[i]){
      if(i<t)hld.add_edge(i,t);
    }
  }
  hld.build();
  auto f=[](int a,int b){return max(a,b);};
  SegmentTree<int> seg(f,-1);
  seg.init(V);
  
  rep(i,q){
    int c;cin >> c;
    // rep(i,V){
    //   cout << seg[i] << " ";
    // }
    // cout << "" << endl;
    if(c==1){
      int u,w;cin >> u >> w;u--;
      W[w]=u;
      u=tecc.blg[u];
      u=hld.vid[u];
      //cout << u << endl;
      que[u].push(w);
      if(seg[u]!=-1){
        que[u].push(seg[u]);
        seg.set_val(u,-1);
      }
      int w_=que[u].top();que[u].pop();
      seg.set_val(u,w_);
    }
    else{
      int s,t;cin >> s >> t;s--;t--;
      s=tecc.blg[s];
      t=tecc.blg[t];
      //cout << hld.vid[s] << " " << hld.vid[t] << endl;
      auto g=[&](int l,int r){return seg.query(l,r);};
      int ans=-1;
      hld.for_each(s,t,[&](int l,int r){
        ans=max(ans,seg.query(l,r));
      });
      cout << ans << endl;
      if(ans==-1) continue; 
      int u_=W[ans];
      u_=cmp[u_];
      u_=hld.vid[u_];
      //cout << u_ << endl;
      seg.set_val(u_,-1);
      if(!que[u_].empty()){
        int w_=que[u_].top();que[u_].pop();
        seg.set_val(u_,w_);
      }
    }
  }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}
0