結果

問題 No.922 東北きりきざむたん
ユーザー yakamotoyakamoto
提出日時 2019-11-08 22:43:53
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 6,100 bytes
コンパイル時間 2,135 ms
コンパイル使用メモリ 184,560 KB
実行使用メモリ 29,052 KB
最終ジャッジ日時 2024-09-15 01:55:20
合計ジャッジ時間 4,987 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 35 ms
12,788 KB
testcase_10 AC 26 ms
6,400 KB
testcase_11 AC 33 ms
10,828 KB
testcase_12 AC 18 ms
13,248 KB
testcase_13 AC 10 ms
6,016 KB
testcase_14 AC 53 ms
18,060 KB
testcase_15 AC 14 ms
14,000 KB
testcase_16 AC 102 ms
19,728 KB
testcase_17 AC 95 ms
19,732 KB
testcase_18 AC 102 ms
19,728 KB
testcase_19 AC 102 ms
19,728 KB
testcase_20 AC 102 ms
19,600 KB
testcase_21 AC 120 ms
20,224 KB
testcase_22 AC 116 ms
20,092 KB
testcase_23 AC 123 ms
19,708 KB
testcase_24 AC 130 ms
19,708 KB
testcase_25 AC 102 ms
20,368 KB
testcase_26 AC 98 ms
20,372 KB
testcase_27 AC 102 ms
20,244 KB
testcase_28 AC 35 ms
16,976 KB
testcase_29 AC 120 ms
29,052 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */


#ifndef SOLUTION_COMMON_H

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PI = pair<int, int>;
template<class T> using V = vector<T>;
using VI = V<int>;
#define _1 first
#define _2 second

#ifdef MY_DEBUG
# define DEBUG(x) x
#else
# define DEBUG(x)
#endif

template<class A, class B>
std::ostream & operator <<(ostream &os, const pair<A, B> &p) {
  os << "(" << p._1 << "," << p._2 << ")";
  return os;
}

template<class T>
inline void debug(T &A) {
  DEBUG(
      for (const auto &a : A) {
        cerr << a << " ";
      }
      cerr << '\n';
  )
}

template<class T, class Func>
inline void debug_with_format(T &A, Func f) {
  DEBUG(
      for (const auto &a : A) {
        cerr << f(a) << " ";
      }
      cerr << '\n';
  )
}

template<class T>
inline void debug_dim2(T &A) {
  DEBUG(
      for (const auto &as : A) {
        debug(as);
      }
  )
}

template<typename ... Args>
inline void debug(const char *format, Args const &... args) {
  DEBUG(
      fprintf(stderr, format, args ...);
      cerr << '\n';
  )
}

template<typename ... Args>
string format(const string &fmt, Args ... args) {
  size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);
  vector<char> buf(len + 1);
  snprintf(&buf[0], len + 1, fmt.c_str(), args ...);
  return string(&buf[0], &buf[0] + len);
}

template<class T1, class T2>
string fmtP(pair<T1, T2> a) {
  stringstream ss;
  ss << "(" << a._1 << "," << a._2 << ")";
  return ss.str();
}

#define SOLUTION_COMMON_H

#endif //SOLUTION_COMMON_H


class UnionFind {
public:
  VI p;
  VI rank;

  UnionFind(int n): p(n), rank(n, 1) {
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
  }

  int unite(int x, int y) {
    int idx = find(x), idy = find(y);
    if (idx == idy) return idx;

    auto merge = [&](int nd, int rt) {
      rank[rt] += rank[nd];
      p[nd] = rt;
      return rt;
    };

    return rank[idx] < rank[idy] ? merge(idx, idy) : merge(idy, idx);
  }

  int find(int x) {
    return p[x] == x ? x : find(p[x]);
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  int count_connected(int x) {
    return rank[find(x)];
  }
};



class LCA {
public:
  int N;
  V<VI> anc;
  VI depth;
  int K;

  LCA(V<VI> &g, int K, VI& routes): N((int)g.size()), anc(K, VI(N)), depth(N), K(K) {
    function<void(int, int)> initParent = [&](int v, int p) {
      anc[0][v] = p;
      depth[v] = v == p ? 0 : depth[p] + 1;
      for (const auto &u : g[v]) {
        if (p != u) initParent(u, v);
      }
    };

    for (const auto &rt : routes) {
      initParent(rt, rt); // rtの親はrtってことにすると処理が楽になる
    }
    for (int k = 1; k < K; ++k) {
      for (int i = 0; i < N; ++i) {
        anc[k][i] = anc[k - 1][anc[k - 1][i]];
      }
    }
  }

  int get_anc(int v, int dist) {
    int i = 0;
    while(dist > 0) {
      if (dist >> i & 1) {
        dist -= 1 << i;
        v = anc[i][v];
      }
      i++;
    }
    return v;
  }

  int operator()(int v, int u) {
    int d = min(depth[v], depth[u]);
    v = get_anc(v, depth[v] - d);
    u = get_anc(u, depth[u] - d);
    if (v == u) return v;

    function<int(int, int, int)> dfs = [&](int v, int u, int s) {
      for (int k = s; k >= 0; --k) {
        if (anc[k][u] != anc[k][v]) {
          return dfs(anc[k][u], anc[k][v], k - 1);
        }
      }
      return anc[0][v];
    };

    return dfs(v, u, K - 1);
  }
};

const int MOD = 1000000007;

class C {
public:
  void solve(std::istream& in, std::ostream& out) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    in >> n >> m >> q;
    V<VI> g(n);
    UnionFind uf(n);

    for (int i = 0; i < m; ++i) {
      int u, v;
      in >> u >> v;
      u--; v--;
      g[u].push_back(v);
      g[v].push_back(u);
      uf.unite(u, v);
    }

    VI routes;
    V<bool> hoge(n);
    for (int i = 0; i < n; ++i) {
      if (!hoge[uf.find(i)]) {
        hoge[uf.find(i)] = true;
        routes.push_back(i);
      }
    }
    LCA lca(g, 20, routes);
    VI cnt(n);
    V<ll> sum(n);
    V<bool> visited(n);

    VI a(q), b(q);
    for (int i = 0; i < q; ++i) {
      in >> a[i] >> b[i];
      a[i]--; b[i]--;
    }

    function<void(int, int)> dfs = [&](int v, int p) {
      visited[v] = true;
      for (const auto &u : g[v]) {
        if (u != p) {
          dfs(u, v);
          cnt[v] += cnt[u];
          sum[v] += sum[u] + cnt[u];
        }
      }
    };

    ll ans = 0ll;

    // 連結成分内の計算
    for (int i = 0; i < q; ++i) {
      if (uf.same(a[i], b[i])) {
        int cp = lca(a[i], b[i]);
        int move = lca.depth[a[i]] + lca.depth[b[i]] - 2 * lca.depth[cp];
        ans += move;
      }
    }
    debug(routes);
    debug("ans:%lld", ans);

    auto calc1 = [&]() {
      for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
          dfs(i, -1);
          ans += sum[i];
        }
      }

      debug(cnt);
      debug(sum);
      debug("ans:%lld", ans);
    };

    function<void(int, int, ll, int)> dfs2 = [&](int v, int p, ll total, int cntTotal) {
      visited[v] = true;
      if (p != -1) {
        int others = cntTotal - cnt[v];
        total += others - cnt[v];
        debug("v:%d cnt[v]:%d total:%d others:%d", v, cnt[v], total, others);
        ans = min(ans, total);
      }
      for (const auto &u : g[v]) {
        if (u != p) {
          dfs2(u, v, total, cntTotal);
        }
      }
    };

    auto calc2 = [&]() {
      fill(visited.begin(), visited.end(), false);
      for (int i = 0; i < n; ++i) {
        if (!visited[i]) dfs2(i, -1, ans, cnt[i]);
      }

      debug(cnt);
      debug(sum);
      debug("ans:%lld", ans);
    };

    // 連結成分をまたぐケースの計算
    for (int i = 0; i < q; ++i) {
      if (!uf.same(a[i], b[i])) {
        cnt[a[i]]++; cnt[b[i]]++;
      }
    }
    calc1();
    calc2();

    out << ans;
  }
};


int main() {
	C solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
0