結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー yakamoto
提出日時 2019-11-08 22:23:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,639 bytes
コンパイル時間 1,952 ms
コンパイル使用メモリ 179,808 KB
実行使用メモリ 20,736 KB
最終ジャッジ日時 2024-09-15 01:36:43
合計ジャッジ時間 5,083 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 15 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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)];
  }
};


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 cnt(n);
    V<ll> sum(n);
    V<bool> visited(n);

    VI a(n), b(n);
    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;
    auto calc1 = [&]() {
      fill(sum.begin(), sum.end(), 0);
      fill(visited.begin(), visited.end(), false);
      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();

    // 連結成分をまたぐケースの計算
    fill(cnt.begin(), cnt.end(), 0);
    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