結果

問題 No.529 帰省ラッシュ
ユーザー hashiryohashiryo
提出日時 2019-06-09 11:35:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 617 ms / 4,500 ms
コード長 6,365 bytes
コンパイル時間 3,216 ms
コンパイル使用メモリ 198,568 KB
実行使用メモリ 47,696 KB
最終ジャッジ日時 2024-10-06 00:01:37
合計ジャッジ時間 9,219 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 7 ms
5,248 KB
testcase_05 AC 7 ms
5,248 KB
testcase_06 AC 7 ms
5,248 KB
testcase_07 AC 7 ms
5,248 KB
testcase_08 AC 340 ms
20,948 KB
testcase_09 AC 346 ms
21,060 KB
testcase_10 AC 444 ms
35,428 KB
testcase_11 AC 459 ms
36,108 KB
testcase_12 AC 289 ms
18,092 KB
testcase_13 AC 246 ms
47,696 KB
testcase_14 AC 294 ms
21,612 KB
testcase_15 AC 617 ms
42,924 KB
testcase_16 AC 617 ms
42,928 KB
testcase_17 AC 474 ms
47,608 KB
testcase_18 AC 484 ms
47,520 KB
testcase_19 AC 454 ms
47,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 998244353;

struct Edge{
  int src,dst;
  Edge(ll s,ll t):src(s),dst(t){}
};
using Edges=vector<Edge>;
using Graph=vector<Edges>;

struct BridgeBlockTree{
    vector<int> index;
    vector<vector<int>> block;
    Edges bridges;
    Graph g;
    BridgeBlockTree(Graph g_){
        ll n=g_.size();
        index.assign(n, -1);
        vector<int> num(n), par(n,-1), cur(n);
        for (int s = 0; s < n; ++s) {
            if (num[s]) continue;
            int time = 0;
            vector<int> snum, path, stack = {s};
            while (!stack.empty()) {
                int u = stack.back();
                if (cur[u] == 0) {
                    num[u] = ++time;
                    path.push_back(u);
                    snum.push_back(num[u]);
                }
                if(cur[u] == (ll)g_[u].size()){
                    if (num[u] == snum.back()){
                        snum.pop_back();
                        block.push_back({});
                        while (1) {
                            int w = path.back(); path.pop_back();
                            block.back().push_back(w);
                            index[w] = block.size()-1;
                            if (u == w) break;
                        }
                    }
                    stack.pop_back();
                }else{
                    int v = g_[u][cur[u]++].dst;
                    if (!num[v]) {
                        par[v] = u;
                        stack.push_back(v);
                    }else if (v != par[u] && index[v] < 0) {
                        while (snum.back() > num[v]) snum.pop_back();
                    }
                }
            }
        }
        ll tn = block.size();
        g.resize(tn);
        for (int u = 0; u < n; ++u)if(par[u] >= 0 && index[u] != index[par[u]]){
            g[index[u]].emplace_back(index[u], index[par[u]]);
            g[index[par[u]]].emplace_back(index[par[u]],index[u]);
            bridges.emplace_back(index[u],index[par[u]]);
        }
    }
    int operator[](const int &k){
        return index[k];
    }
};

struct HLDecomposition{
private:
    int t;
    void dfs_size(int v=0){
        size[v]=1;
        for(Edge& e:g[v]){
            if(par[e.dst]>=0){
                swap(e,g[v].back());
                if(e.dst==g[v].back().dst)continue;
            }
            par[e.dst]=v;
            dfs_size(e.dst);
            size[v]+=size[e.dst];
            if(size[e.dst]>size[g[v][0].dst]){
                swap(e,g[v][0]);
            }
        }
    }
    void dfs_hld(int v=0,int d=0){
        in[v] = t++;
        inv[in[v]]=v;
        dep[v] = d;
        for(Edge& e:g[v]){
            if(par[e.dst]!=v)continue;
            head[e.dst]=(e.dst==g[v][0].dst?head[v]:e.dst);
            dfs_hld(e.dst,d+1);
        }
        out[v]=t;
    }
public:
    int V;
    Graph g;
    vector<int> dep,par,head,size,inv;
    vector<int> in,out;
    HLDecomposition(int size_)
    :t(0),V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){}
    HLDecomposition(Graph g_)
    :t(0),V(g_.size()),g(g_),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){}
    void add_edge(int u,int v){
        g[u].emplace_back(u,v);
        g[v].emplace_back(v,u);
    }
    void build(int root=0){
        par[root]=0;
        dfs_size(root);
        par[root]=-1;
        dfs_hld(root);
    }
    int lca(int u,int v){
        while(1){
            if(in[u]>in[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)];
    }
    int operator[](const int &k){
        return in[k];
    }
};

template <typename M>
struct SegmentTree{
    using T = typename M::T;
    int n;
    vector<T> dat;
    SegmentTree(){}
    SegmentTree(int n_){init(n_);}
    SegmentTree(const vector<T> &v){build(v);}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,M::ti());
    }
    void build(const vector<T> &v){
        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]=M::f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
        dat[k+=n]=x;
        while(k>>=1)
            dat[k]=M::f(dat[(k<<1)|0],dat[(k<<1)|1]);
    }
    //[a,b)
    T query(int a,int b,int k=1,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l) return M::ti();
        if(a<=l&&r<=b) return dat[k];
        T vl=query(a,b,k*2,l,(l+r)/2);
        T vr=query(a,b,k*2+1,(l+r)/2,r);
        return M::f(vl,vr);
    }
    T operator[](const int &k) const {return dat[k + n];}
};

struct RmaxQ {
    struct T{
      ll val,idx;
      T(ll v,ll i):val(v),idx(i){}
    };
    static T ti() { return {-1,0}; }
    static T f(const T& l, const T & r) { return l.val>r.val? l:r; }
};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,M,Q;cin>>N>>M>>Q;
  Graph g(N);
  for(ll i=0;i<M;i++){
    ll x,y;cin>>x>>y;x--;y--;
    g[x].emplace_back(x,y);
    g[y].emplace_back(y,x);
  }
  BridgeBlockTree bbt(g);
  HLDecomposition hld(bbt.g);
  hld.build();
  SegmentTree<RmaxQ> seg(hld.V);
  for(ll i=0;i<hld.V;i++){
    seg.set_val(hld[i],{-1,hld[i]});
  }
  vector<priority_queue<ll>> que(hld.V);
  for(ll i=0;i<hld.V;i++){
    que[i].push(-1);
  }
  for(ll q=0;q<Q;q++){
    ll op;cin>>op;
    if(op&1){
      ll U,W;cin>>U>>W;U--;
      ll u=bbt[U];
      que[hld[u]].push(W);
      seg.set_val(hld[u],{que[hld[u]].top(),hld[u]});
    }else{
      ll S,T;cin>>S>>T;S--;T--;
      ll u=bbt[S],v=bbt[T];
      RmaxQ::T ans=RmaxQ::ti();
      while(1){
        if(hld[u]>hld[v])swap(u,v);
        ans = RmaxQ::f(ans,seg.query(max(hld[u],hld[hld.head[v]]),hld[v]+1));
        if(hld.head[u]!=hld.head[v])v=hld.par[hld.head[v]];
        else break;
      }
      cout<<ans.val<<endl;
      if(ans.val>=0){
        que[ans.idx].pop();
        seg.set_val(ans.idx,{que[ans.idx].top(),ans.idx});
      }
    }
  }

  return 0;
}
0