Submission #909636

#	Time	Username	Problem	Language	Result	Execution time	Memory
909636		MilosMilutinovic	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	220 ms	10584 KiB

friends

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> u(m);
  vector<int> v(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i];
    --u[i]; --v[i];
    g[u[i]].push_back(v[i]);
  }
  vector<int> par(n);
  vector<int> sz(n, 1);
  iota(par.begin(), par.end(), 0);
  function<int(int)> GetPar = [&](int x) {
    return par[x] == x ? x : par[x] = GetPar(par[x]);
  };
  auto Merge = [&](int x, int y) {
    x = GetPar(x);
    y = GetPar(y);
    if (x == y) {
      return;
    }
    if (sz[x] > sz[y]) {
      swap(x, y);
    }
    sz[y] += sz[x];
    par[x] = y;
  };
  for (int foo = 0; foo < 20; foo++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < (int) g[i].size(); j++) {
        Merge(g[i][0], g[i][j]);
      }
      if (sz[GetPar(i)] > 1) {
        for (int j : g[i]) {
          Merge(i, j);
        }
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (GetPar(i) == i) {
      ans += sz[i] * 1LL * (sz[i] - 1);
    }
  }
  for (int i = 0; i < m; i++) {
    if (GetPar(u[i]) != GetPar(v[i])) {
      ans += 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65