結果

問題 No.529 帰省ラッシュ
コンテスト
ユーザー SSRS
提出日時 2022-05-15 03:16:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 791 ms / 4,500 ms
コード長 4,632 bytes
コンパイル時間 2,692 ms
コンパイル使用メモリ 193,304 KB
実行使用メモリ 35,540 KB
最終ジャッジ日時 2024-07-23 14:45:47
合計ジャッジ時間 12,572 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
struct two_edge_connected_components{
  vector<int> tcc;
  int cnt;
  two_edge_connected_components(vector<vector<int>> &E){
    int N = E.size();
    vector<int> d(N, -1);
    d[0] = 0;
    vector<int> imos(N, 0);
    dfs1(E, d, imos);
    tcc = vector<int>(N, -1);
    tcc[0] = 0;
    cnt = 1;
    dfs2(E, imos);
  }
  void dfs1(vector<vector<int>> &E, vector<int> &d, vector<int> &imos, int v = 0){
    for (int w : E[v]){
      if (d[w] == -1){
        d[w] = d[v] + 1;
        dfs1(E, d, imos, w);
        imos[v] += imos[w];
      } else if (d[w] < d[v] - 1){
        imos[v]++;
        imos[w]--;
      }
    }
  }
  void dfs2(vector<vector<int>> &E, vector<int> &imos, int v = 0){
    for (int w : E[v]){
      if (tcc[w] == -1){
        if (imos[w] > 0){
          tcc[w] = tcc[v];
        } else {
          tcc[w] = cnt;
          cnt++;
        }
        dfs2(E, imos, w);
      }
    }
  }
  int operator [](int v){
    return tcc[v];
  }
  int count(){
    return cnt;
  }
};
struct segment_tree{
  int N;
  vector<pair<int, int>> ST;
  segment_tree(){
  }
  segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<pair<int, int>>(N * 2 - 1, make_pair(-1, 0));
  }
  void update(int i, pair<int, int> P){
    i += N - 1;
    ST[i] = P;
    while (i > 0){
      i = (i - 1) / 2;
      ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  pair<int, int> range_max(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return make_pair(-1, 0);
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
    }
  }
  pair<int, int> range_max(int L, int R){
    return range_max(L, R, 0, 0, N);
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  vector<int> id;
  segment_tree ST;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c): p(p){
    int N = c.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
    ST = segment_tree(N);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  void update(int v, int x){
    ST.update(in[v], make_pair(x, v));
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  pair<int, int> path_max(int u, int v){
    int w = lca(u, v);
    pair<int, int> ans = make_pair(-1, 0);
    while (next[u] != next[w]){
      ans = max(ans, ST.range_max(in[next[u]], in[u] + 1));
      u = p[next[u]];
    }
    ans = max(ans, ST.range_max(in[w], in[u] + 1));
    while (next[v] != next[w]){
      ans = max(ans, ST.range_max(in[next[v]], in[v] + 1));
      v = p[next[v]];
    }
    ans = max(ans, ST.range_max(in[w], in[v] + 1));
    return ans;
  }
};
int main(){
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }
  two_edge_connected_components G(E);
  int V = G.count();
  vector<vector<int>> E2(V);
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (G[i] != G[j]){
        E2[G[i]].push_back(G[j]);
      }
    }
  }
  vector<int> p(V, -1);
  vector<vector<int>> c(V);
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (int w : E2[v]){
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        q.push(w);
      }
    }
  }
  vector<priority_queue<int>> pq(V);
  for (int i = 0; i < V; i++){
    pq[i].push(-1);
  }
  heavy_light_decomposition H(p, c);
  for (int i = 0; i < Q; i++){
    int t;
    cin >> t;
    if (t == 1){
      int U, W;
      cin >> U >> W;
      U--;
      pq[G[U]].push(W);
      H.update(G[U], pq[G[U]].top());
    }
    if (t == 2){
      int S, T;
      cin >> S >> T;
      S--;
      T--;
      pair<int, int> P = H.path_max(G[S], G[T]);
      cout << P.first << endl;
      if (P.first != -1){
        int x = P.second;
        pq[x].pop();
        H.update(x, pq[x].top());
      }
    }
  }
}
0