結果

問題 No.529 帰省ラッシュ
ユーザー ferinferin
提出日時 2018-08-13 23:43:47
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 749 ms / 4,500 ms
コード長 8,299 bytes
コンパイル時間 3,897 ms
コンパイル使用メモリ 199,052 KB
実行使用メモリ 69,872 KB
最終ジャッジ日時 2023-10-24 16:54:17
合計ジャッジ時間 10,465 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 7 ms
4,348 KB
testcase_05 AC 7 ms
4,348 KB
testcase_06 AC 7 ms
4,348 KB
testcase_07 AC 7 ms
4,348 KB
testcase_08 AC 486 ms
38,316 KB
testcase_09 AC 480 ms
38,292 KB
testcase_10 AC 543 ms
45,928 KB
testcase_11 AC 570 ms
46,232 KB
testcase_12 AC 425 ms
36,152 KB
testcase_13 AC 424 ms
69,872 KB
testcase_14 AC 476 ms
42,884 KB
testcase_15 AC 740 ms
50,556 KB
testcase_16 AC 749 ms
50,556 KB
testcase_17 AC 565 ms
59,840 KB
testcase_18 AC 569 ms
60,368 KB
testcase_19 AC 563 ms
57,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct HLDecomposition {
  int n, pos;
  VVI g;
  VI vid,   // HL分解後のグラフでのid
     head,  // 頂点が属するheavy-pathのheadのid
     sub,   // 部分木のサイズ
     hvy,   // heavy-path上での次の頂点のid
     par,   // 親のid
     depth, // 深さ
     inv,   // HL分解前のグラフのid（添え字が分解後のid）
     type;  // 森をHL分解するときの属する木の番号

  HLDecomposition(){}
  HLDecomposition(int sz):
    n(sz), pos(0), g(n),
    vid(n,-1), head(n), sub(n,1), hvy(n,-1),
    par(n), depth(n), inv(n), type(n) {}

  // 辺の追加
  void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
  // HL分解の構築を行う
  void build(VI rs=VI(1,0)) {
    int c=0;
    for(int r: rs){
      dfs(r);
      bfs(r, c++);
    }
  }
  // 根rtからdfsして部分木の大きさ、heavy-edgeの判定などをする
  void dfs(int rt) {
    stack<PII> st;
    par[rt] = -1;
    depth[rt] = 0;
    st.emplace(rt, 0);
    while(!st.empty()) {
      int v = st.top().first;
      int &i = st.top().second;
      if(i < (int)g[v].size()) {
      	int u = g[v][i++];
      	if(u == par[v]) continue;
      	par[u] = v;
      	depth[u] = depth[v]+1;
      	st.emplace(u,0);
      } else {
      	st.pop();
      	int ma = 0;
      	for(int u: g[v]){
      	  if(u == par[v]) continue;
      	  sub[v] += sub[u];
      	  if(ma < sub[u]) ma = sub[u], hvy[v] = u;
      	}
      }
    }
  }
  // 根r、c番目の木についてchainについての情報をまとめる
  void bfs(int r, int c) {
    int &k = pos;
    queue<int> que;
    que.push(r);
    while(que.size()) {
      int h = que.front(); que.pop();
      for(int i=h; i!=-1; i=hvy[i]) {
      	type[i] = c;
      	vid[i] = k++;
      	inv[vid[i]] = i;
      	head[i] = h;
	      for(int j: g[i]) {
          if(j!=par[i] && j!=hvy[i]) que.push(j);
        }
      }
    }
  }
  // 頂点に対する処理 [u,v] 開区間なので注意!!!
  void for_each(int u, int v, const function<void(int, int)>& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      // [max(vid[head[v]],vid[u]), vid[v]] の区間についての操作を行う
      f(max(vid[head[v]], vid[u]), vid[v]);
      if(head[u]!=head[v]) v = par[head[v]];
      else break;
    }
  }
  // 辺に対する処理 [u,v] 開区間なので注意!!!
  void for_each_edge(int u, int v, const function<void(int, int)>& f) {
    while(1) {
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]!=head[v]) {
	      f(vid[head[v]], vid[v]);
        v = par[head[v]];
      } else {
	      if(u!=v) f(vid[u]+1, vid[v]);
	      break;
      }
    }
  }
  // 頂点u, vのLCA
  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]];
    }
  }
  // 頂点u, vの距離
  int distance(int u, int v){
    return depth[u] + depth[v] - 2*depth[lca(u,v)];
  }
};

struct twoEdgeComponents {
    int n;
    vector<vector<int>> g;        // グラフの隣接リスト
    vector<int> cmp;              // 頂点iがどの連結成分に属するか
    vector<vector<int>> each_bcc; // i番目の連結成分の属する頂点
    vector<pair<int,int>> bridge; // i番目の橋
    vector<int> order;
    vector<bool> inS;
    stack<int> roots, S;

    twoEdgeComponents() {}
    twoEdgeComponents(int n_) : n(n_), g(VVI(n)) {}
    twoEdgeComponents(vector<vector<int>> g_) : n(g_.size()), g(g_) {}

    void add_edge(int p, int q) {
        g[p].push_back(q);
        g[q].push_back(p);
    }

    void dfs(int cur, int prev, int &k) {
        order[cur] = ++k;
        S.push(cur); inS[cur] = true;
        roots.push(cur);

        for(auto to: g[cur]) {
            if(order[to]==0) dfs(to, cur, k);
            else if(to!=prev && inS[to]) {
                while(order[roots.top()] > order[to]) roots.pop();
            }
        }

        if(cur == roots.top()) {
            if(prev!=-1) bridge.push_back({prev, cur});
            vector<int> bcc;
            while(1) {
                int node = S.top(); S.pop(); inS[node] = false;
                bcc.push_back(node);
                if(node==cur) break;
            }
            each_bcc.push_back(bcc);
            roots.pop();
        }
    }
    // 二重辺連結成分分解を行う
    void bcc() {
        order.assign(n, 0);
        inS.assign(n, false);
        cmp.assign(n, -1);
        int k = 0;
        for(int i=0; i<n; ++i) {
            if(order[i] == 0) {
                dfs(i, -1, k);
            }
        }
        for(int i=0; i<(int)each_bcc.size(); ++i) {
            for(auto j: each_bcc[i]) {
                cmp[j] = i;
            }
        }
    }
    // 分解したあとの木を求める
    vector<vector<int>> getbcc() {
        vector<vector<int>> h(each_bcc.size(), vector<int>());
        for(auto i: bridge) {
            int a = cmp[i.first], b = cmp[i.second];
            h[a].push_back(b);
            h[b].push_back(a);
        }
        return h;
    }
};

template <typename monoid>
class segmentTree {
public:
  using M = monoid;
  using T = typename M::value_type;

  int sz;
  vector<T> x;

  segmentTree(int n = 1e5) {
    sz = 1; while(sz < n) sz *= 2;
    init();
  }
  void init() { x.assign(sz*2, M::id()); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return M::id();
    if(a <= l && r <= b) return x[k];
    return M::f(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, sz);}
  // 点更新
  void update(int i, const T &val) {
    i += sz-1;
    x[i] = M::g(x[i], val);
    while(i > 0) {
      i = (i-1) / 2;
      x[i] = M::f(x[i*2+1], x[i*2+2]);
    }
  }
};

template <typename T>
struct max_monoid {
  using value_type = T;
  static constexpr T id() { return std::numeric_limits<T>::min(); }
  static T f(const T &a, const T &b) { return max(a, b); }
  static T g(const T &a, const T &b) { return b; }
};
template <typename T>
using rmq = segmentTree<max_monoid<T>>;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m, q;
  cin >> n >> m >> q;
  VI a(m), b(m);
  VVI g(n);
  REP(i, m) {
    cin >> a[i] >> b[i]; a[i]--, b[i]--;
    g[a[i]].PB(b[i]);
    g[b[i]].PB(a[i]);
  }
  twoEdgeComponents bcc(g);
  bcc.bcc();

  int sz = bcc.bridge.size()+1;
  HLDecomposition hld(sz);
  for(auto i: bcc.bridge) {
    hld.add_edge(bcc.cmp[i.first], bcc.cmp[i.second]);
  }
  hld.build();

  vector<priority_queue<int>> que(sz);
  rmq<int> seg(sz);

  map<int,int> mp;
  REP(i, q) {
    int type; cin >> type;
    // 追加
    if(type == 1) {
      int u, w; cin >> u >> w; u--;
      int ver = hld.vid[bcc.cmp[u]];
      mp[w] = ver;
      if(que[ver].empty() || que[ver].top()<w) seg.update(ver, w);
      que[ver].push(w);
    }
    else {
      int s, t; cin >> s >> t; s--, t--;
      s = bcc.cmp[s], t = bcc.cmp[t];
      int ans = -1;
      hld.for_each(s, t, [&](int l, int r){
        chmax(ans, seg.query(l, r+1));
      });
      cout << ans << endl;
      if(ans == -1) continue;
      int ver = mp[ans];
      que[ver].pop();
      int cost = que[ver].size()?que[ver].top():-1;
      seg.update(ver, cost);
    }
  }

  return 0;
}
0