結果

問題 No.922 東北きりきざむたん
ユーザー nn1k_nn1k_
提出日時 2019-11-08 23:23:39
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,053 bytes
コンパイル時間 2,390 ms
コンパイル使用メモリ 190,568 KB
実行使用メモリ 36,016 KB
最終ジャッジ日時 2023-10-13 04:59:21
合計ジャッジ時間 8,714 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 RE -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 RE -
testcase_15 RE -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 127 ms
36,016 KB
testcase_29 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i64 = int64;

#define rep(i,N) for(int i=0;i<(int)(N); ++i)

const int inf = 1 << 30;
const int64 inf64 = 1ll << 60;

template< typename G >
struct DoublingLowestCommonAncestor {
  const int LOG;
  vector< int > dep;
  const G &g;
  vector< vector< int > > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector< int >(g.size(), -1));
  }

  void dfs(int idx, int par, int d) {
    table[0][idx] = par;
    dep[idx] = d;
    for(auto &to : g[idx]) {
      if(to != par) dfs(to, idx, d + 1);
    }
  }

  void build() {
    dfs(0, -1, 0);
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  pair<int, int> query(int u, int v) {
     if(dep[u] > dep[v]) swap(u, v);
     int iu = u, iv = v;
     for(int i = LOG - 1; i >= 0; --i) {
        if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
     }
     if(u == v) {
        return make_pair(u, dep[iv] - dep[iu]);
     }
      
     iu = u, iv = v;

     for(int i = LOG - 1; i >= 0; --i) {
        if(table[i][u] != table[i][v]) {
           u = table[i][u];
           v = table[i][v];
        }
     }
     
     return make_pair(table[0][u], dep[iu] + dep[iv] - 2 * dep[table[0][u]]);
  }
};

int main() {
   using P = pair<int, int>;

   int N, M, Q; cin >> N >> M >> Q;
   vector<vector<int>> G(N);
   rep(i, M) {
      int u, v; cin >> u >> v, u--, v--;
      G[u].emplace_back(v);
      G[v].emplace_back(u);
   }

   vector<int> a(Q), b(Q);
   rep(i, Q) cin >> a[i] >> b[i], a[i]--, b[i]--;
   
   vector<DoublingLowestCommonAncestor<vector<vector<int>>>> lcas;

   vector<int> idx(N, -1);
   int v = 0;
   vector<int> convert(N);
   vector<vector<vector<int>>> gs;
   rep(i, N) {
      if(idx[i] != -1) continue;
      idx[i] = v++;
      stack<int> stk;
      stk.emplace(i);
      convert[i] = 0;
      vector<vector<int>> g;
      g.emplace_back(vector<int>());
      int num = 0;
      while(!stk.empty()) {
         int i = stk.top(); stk.pop();
         for(auto &e : G[i]) {
            if(idx[e] != -1) continue;
            idx[e] = idx[i];
            stk.emplace(e);
            convert[e] = ++num;
            g.emplace_back(vector<int>());
            g[convert[i]].emplace_back(convert[e]);
            g[convert[e]].emplace_back(convert[i]);
         }
      }
      lcas.emplace_back(DoublingLowestCommonAncestor<vector<vector<int>>>(g));
      gs.emplace_back(g);
      lcas.back().build();
   }
   
   /*
   rep(i, N) cout << idx[i] << " ";
   cout << endl;
   rep(i, N) cout << convert[i] << " ";
   cout << endl;
   */
   
   vector<int> w(N);

   i64 ans = 0;
   rep(i, Q) {
      if(idx[a[i]] == idx[b[i]]) {
         P p = lcas[idx[a[i]]].query(convert[a[i]], convert[b[i]]);
         //cout << a[i] << " " << b[i] << endl;
         //cout << convert[a[i]] << " " << convert[b[i]] << endl;
         //cout << p.first << endl;
         ans += p.second;
      } else {
         w[a[i]]++;
         w[b[i]]++;
      }
   }
   
   vector<P> root(lcas.size(), P(-1, -1));
   rep(i, N) {
      if(root[idx[i]].second < w[i]) {
         root[idx[i]] = P(convert[i], w[i]);
      }
   }
   
   vector<vector<int>> d(gs.size());
   rep(i, gs.size()) {
      d[i].assign(gs[i].size(), inf);
      stack<int> stk;
      stk.emplace(root[i].first);
      d[i][root[i].first] = 0;
      while(!stk.empty()) {
         int idx = stk.top();
         stk.pop();
         for(auto &e : gs[i][idx]) {
            if(d[i][e] <= d[i][idx] + 1) continue;
            d[i][e] = d[i][idx] + 1;
            stk.emplace(e);
         }
      }
   }

   rep(i, N) {
      if(idx[a[i]] == idx[b[i]]) continue;
      if(w[i] == 0) continue;
      ans += d[idx[a[i]]][convert[a[i]]] * w[a[i]];
      ans += d[idx[b[i]]][convert[b[i]]] * w[b[i]];
   }

   cout << ans << endl;
}
0