結果

問題 No.529 帰省ラッシュ
ユーザー n_vipn_vip
提出日時 2017-06-09 23:25:43
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 718 ms / 4,500 ms
コード長 10,227 bytes
コンパイル時間 2,610 ms
コンパイル使用メモリ 146,192 KB
実行使用メモリ 98,552 KB
最終ジャッジ日時 2024-12-16 06:34:42
合計ジャッジ時間 10,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string &s, char c){vector<string> v;int d=0,f=0;string t;for(char c:s){if(!d&&c==',')v.pb(t),t="";else t+=c;if(c=='\"'||c=='\'')f^=1;if(!f&&c=='(')++d;if(!f&&c==')')--d;}v.pb(t);return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
const ll MOD=1e9+7;
class Bcc{
  vector<int> num,inS;
  stack<int> roots,st;
  int cnt;
public:
  vv<int> bcc,tree,tedge;
  vector<int> brdg,inv; 
  void dfs(const vv<int> &g,const vector<pii> &es,int v,int e){
    num[v]=++cnt;
    st.push(v); inS[v]=1; roots.push(v);
    for(const int &i:g[v])if(i!=e){
	int w=es[i].X+es[i].Y-v;
	if(!num[w]){
	  dfs(g,es,w,i);
	}else if(inS[w]){
	  while(num[roots.top()]>num[w]) roots.pop();
	}
      }
    if(v==roots.top()){
      brdg.pb(e);
      bcc.pb(vector<int>());
      while(1){
	int w=st.top(); st.pop(); inS[w]=0;
	bcc.back().pb(w);
	if(v==w) break;
      }
      roots.pop();
    }
  }
  
  Bcc(vv<int> &g,vector<pii> es){
    const int n=g.size();
    num.resize(n); inS.resize(n);
    int cnt=0;
    rep(i,n)if(!num[i]){
      dfs(g,es,i,-1);
      brdg.pop_back();
    }
    const int m=bcc.size();
    inv.resize(n);
    rep(i,m) for(const int &v:bcc[i]) inv[v]=i;
    for(pii &p:es){p.X=inv[p.X]; p.Y=inv[p.Y];}
    //sort(all(es)); UNIQUE(es);
    tree.resize(m); tedge.resize(m);
    int i=0;
    for(const pii &p:es){
      if(p.X!=p.Y){
	tree[p.X].pb(p.Y);
	tree[p.Y].pb(p.X);
	tedge[p.X].pb(i);
	tedge[p.Y].pb(i);
      }
      ++i;
    }
  }
};
const int MAX_N=(1<<18);
const ll INF=(1ll<<60);
int nn=MAX_N;

struct Seg{
 int mn,ind;
  Seg(int d=0,int i=1000000){
    mn=d;
    ind=i;
  }
  static Seg e;
};
Seg Seg::e=Seg();

Seg operator+(Seg l,Seg r){
  if(l.mn>r.mn) return l;
  return r;
}
//ostream& operator<<(ostream &os, const Seg &t) { return os<<"["<<t.mn<<")";}
template<class T=Seg> void upd(int k,T a,vector<T> &dat){
  k+=dat.size()/2-1;
  dat[k]=a;
  while(k>0){
    k=(k-1)/2;
    dat[k]=dat[k*2+1]+dat[k*2+2];
  }
}

//(l,r,0,0,nn)
template<class T=Seg> T query(int a,int b,const vector<T> &dat,int k=0,int l=0,int r=-1){
  if(r<0) r=dat.size()/2;
  if(r<=a || b<=l)return T::e;
  if(a<=l && r<=b) return dat[k];
  T lv=query(a,b,dat,k*2+1,l,(l+r)/2) ,rv= query(a,b,dat,k*2+2,(l+r)/2,r);
  return lv+rv;
}

template<class T> class RMQ{
  vv<T> vals;
public:
  inline T get(int l,int r){//[l,r]
    if(l==r)return vals[0][l];
    const int d=31-__builtin_clz(l^r); //left-most distinct bit
    return min(vals[d][l],vals[d][r]);
  }
  RMQ(){};
  RMQ(vector<T> &v,T e=-MOD){ init(v,e); }
  void init(vector<T> &v,T e){
    int n=v.size();
    int d=1,N=2;
    while(N<n) N*=2, ++d;
    vals.resize(d,vector<T>(N,e));
    rep(i,n) vals[0][i]=v[i];
    reps(i,1,d)rep(j,N){
      const int b=(j>>i|1)<<i;
      vals[i][j]=j>>i&1?get(b,j):get(j,b-1);
    }
  }
};

typedef vv<int> Graph;
class Lca{
public:
  vector<int> dep,cld;
  vector<pii> et;
  vector<int> l,r;
  vector<ll> wdep;
  vector<int> par;
  const int LOGN=20;
  int weighted;
  vv<int> wei;
  RMQ<pii> rmq;
  void dfs(const Graph &g,int root){
    int n=g.size();
    vector<int> vst(n);
    stack<int> st; st.push(root);
    while(!st.empty()){
      int v=st.top(); st.pop();
      if(vst[v]==1){
	vst[v]=2;
	r[v]=et.size()-1;
	rep(i,g[v].size())if(g[v][i]!=par[v])
	  cld[v]+=cld[g[v][i]]+1;
	if(par[v]>=0) et.eb(dep[par[v]],par[v]);
      }else if(vst[v]==0){
	st.push(v);
	vst[v]=1;
	l[v]=et.size(); et.eb(dep[v],v);
	rep(i,g[v].size())if(!vst[g[v][i]]){
	  dep[g[v][i]]=dep[v]+1;
	  wdep[g[v][i]]=wdep[v]+(weighted?wei[v][i]:1);
	  par[g[v][i]]=v;
	  st.push(g[v][i]);
	}
      }
    }
  }
  
  Lca(const Graph &g):weighted(0){
    int n=g.size();
    par.resize(n);
    dep.resize(n); wdep.resize(n); cld.resize(n); l.resize(n); r.resize(n); dfs(g,0);
    rmq.init(et,pii(MOD,0));
    // rep(i,LOGN-1)rep(v,n)
    //   par[v][i+1]=par[v][i]<0?-1:par[par[v][i]][i];
  }
  Lca(const vv<pii> &h):weighted(1){
    int n=h.size();
    vv<int> g(n);
    wei.resize(n);
    rep(i,n) for(pii x:h[i]){
      g[i].pb(x.X);
      wei[i].pb(x.Y);
    }
    par.resize(n);
    dep.resize(n); wdep.resize(n); cld.resize(n); l.resize(n); r.resize(n); dfs(g,0);
    rmq.init(et,pii(MOD,0));
    // rep(i,LOGN-1)rep(v,n)
    //   par[v][i+1]=par[v][i]<0?-1:par[par[v][i]][i];
  }
  
  int LCA(int v,int w){
    v=l[v]; w=l[w];
    if(v>w) swap(v,w);
    return rmq.get(v,w).Y;
  }
  ll dist(int v,int w){return wdep[v]+wdep[w]-2*wdep[LCA(v,w)];}
};

class HL{
  Lca lcaTree;
  vector<pii> parh;
  int isEdge,n;
public:
  vv<int> mems,edgel;
  vector<pii> inv;
  vv<int> h;
  vector<int> hvy,par,etov;
  vv<Seg> dats;
  void dfs2(const Graph &g,int v,int p,vector<int> &usd,vector<int> &mem,vector<int> &edges,vector<int> &edgel){
    while(1){
      if(usd[v])return;
      usd[v]=1; mem.pb(v);
      edgel.pb(edges.size());
      if(g[v].size()-(p>=0)==0)
	return;
      rep(i,g[v].size())if(g[v][i]!=p && i!=hvy[v])
	edges.pb(g[v][i]);
      p=v; v=g[v][hvy[v]];
    }
  }
  void HLDec(const Graph &g){
    int n=g.size();
    inv.resize(n);
    vector<int> usd(n);
    rep(i,n)if(!usd[i]){
      mems.pb(vector<int>()); h.pb(vector<int>()); edgel.pb(vector<int>());
      dfs2(g,i,par[i],usd,mems.back(),h.back(),edgel.back());
      rep(j,mems.back().size())
	inv[mems.back()[j]]=pii(h.size()-1,j);
    }
    rep(i,h.size())for(int &v:h[i]) v=inv[v].X;
  }
  void dfs(const Graph &g){
    int n=g.size();
    hvy.resize(n); par.resize(n,-1);
    vector<pii> mx(n);
    vector<int> sum(n,1),vst(n);
    stack<int> st; st.push(0);
    while(!st.empty()){
      int v=st.top(); st.pop();
      if(vst[v]==1){
	vst[v]=2;
	rep(i,g[v].size())if(g[v][i]!=par[v]){
	  sum[v]+=sum[g[v][i]];
	  mx[v]=max(mx[v],pii(sum[g[v][i]],i));
	}
	hvy[v]=mx[v].Y;
      }else if(vst[v]==0){
	st.push(v); vst[v]=1;
	rep(i,g[v].size())if(!vst[g[v][i]]){
	  par[g[v][i]]=v;
	  st.push(g[v][i]);
	}
      }
    }
  }

  void constSegTree(const vector<Seg> &vals){
    int m=h.size();
    dats.resize(m);
    rep(i,m){
      int nn=1;
      while(nn<mems[i].size()) nn<<=1;
      dats[i].resize(2*nn,Seg());
      rep(j,mems[i].size())
	dats[i][nn-1+j]=vals[mems[i][j]];
      rrep(j,nn-1) dats[i][j]=dats[i][2*j+1]+dats[i][2*j+2];
    }
    parh.resize(m,pii(-1,0));
    rep(i,n)if(inv[i].Y==0 && i){
      parh[inv[i].X]=inv[lcaTree.par[i]];
    }
  }
  void HLcommon(const Graph &g,const vector<Seg> &vals){
    n=g.size();
    dfs(g);
    HLDec(g);
    constSegTree(vals);
  }
  HL(const Graph &g,const vector<Seg> &vals):lcaTree(g){
    isEdge=0;
    HLcommon(g,vals);
  }
  HL(const Graph &g,const vector<pii> &es,const vector<Seg> &val):lcaTree(g){
    n=g.size();
    isEdge=1;
    etov.resize(n);
    vector<Seg> vals(n);
    rep(i,n-1){
      if(lcaTree.dep[es[i].X]>lcaTree.dep[es[i].Y])
	etov[i]=es[i].X;
      else
	etov[i]=es[i].Y;
      vals[etov[i]]=val[i];
    }
    HLcommon(g,vals);
  }
  void upd(int v,Seg val){
    ::upd(inv[v].Y,val,dats[inv[v].X]);
  }
  //根の方に降りていく処理
  Seg sumV(vv<Seg> &dats,int lca,int cld,int clopen){
    if(lca<0 || cld<0)return Seg::e;
    Seg re=Seg::e;
    for(pii pos=inv[cld];pos.X!=-1;pos=parh[pos.X]){
      if(pos.X==inv[lca].X){
	re=query(inv[lca].Y+clopen,pos.Y+1,dats[pos.X])+re;
	break;
      }else{
	re=query(0,pos.Y+1,dats[pos.X])+re;
      }
      //cout<<pos<<":"<<re<<endl;
    }
    return re;
  }
  Seg sum(int a,int b){
    int lca=lcaTree.LCA(a,b);
    return sumV(dats,lca,a,1)+sumV(dats,lca,b,isEdge);
  }
};
int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,m,q;
  cin>>n>>m>>q;
  vv<int> g(n);
  vector<pii> es(m);
  rep(i,m){
    int x,y;
    cin>>x>>y; --x; --y;
    es[i]=pii(x,y);
    g[x].pb(i); g[y].pb(i);
  }
  Bcc h(g,es);
  int N=h.tree.size();
  vector<Seg> init(N);
  rep(i,N) init[i]=Seg(0,i);
  HL hl(h.tree,init);
  vector<priority_queue<int>> pqs(N);
  rep(i,N) pqs[i].push(0);
  while(q--){
    int t,x,y;
    cin>>t>>x>>y; --x;
    if(t==1){
      int t=h.inv[x];
      int tmp=pqs[t].top();
      pqs[t].push(y);
      if(tmp!=pqs[t].top()) hl.upd(t,Seg(pqs[t].top(),t));
    }else{ --y;
      Seg ret=hl.sum(h.inv[x],h.inv[y]);
      if(ret.mn){
	cout<<ret.mn<<endl;
	int tmp=pqs[ret.ind].top();
	pqs[ret.ind].pop();
	if(tmp!=pqs[ret.ind].top()) hl.upd(ret.ind,Seg(pqs[ret.ind].top(),ret.ind));
      }else{
	cout<<-1<<endl;
      }
    }
  }
  return 0;
}
0