Submission #156092

#	Time	Username	Problem	Language	Result	Execution time	Memory
156092		IOrtroiii	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	112 ms	7164 KiB

friends

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m;
vector<int> g[N];
int par[N];
int sz[N];
bool visit[N];

int find(int v) {
   if (par[v] != v) {
      par[v] = find(par[v]);
   }
   return par[v];
}

void merge(int v, int u) {
   v = find(v);
   u = find(u);
   if (v == u) {
      return;
   } else {
      par[u] = v;
      sz[v] += sz[u];
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   int n, m;
   cin >> n >> m;
   for (int i = 1; i <= m; ++i) {
      int v, u;
      cin >> v >> u;
      g[v].emplace_back(u);
   }
   iota(par + 1, par + n + 1, 1);
   fill(sz + 1, sz + n + 1, 1);
   for (int i = 1; i <= n; ++i) {
      for (int j = 0; j + 1 < (int) g[i].size(); ++j) {
         merge(g[i][j], g[i][j + 1]);
      }
   }
   queue<int> q;
   for (int i = 1; i <= n; ++i) {
      if (sz[find(i)] > 1) {
         visit[i] = true;
         q.emplace(i);
      }
   }
   while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto u : g[v]) {
         if (!visit[u]) {
            visit[u] = true;
            q.emplace(u);
         }
         merge(v, u);
      }
   }
   long long ans = 0;
   for (int i = 1; i <= n; ++i) {
      if (par[i] == i) {
         ans += (long long) sz[i] * (sz[i] - 1);
      }
   }
   for (int i = 1; i <= n; ++i) {
      for (int j : g[i]) {
         if (find(i) != find(j)) {
            ++ans;
         }
      }
   }
   cout << ans << "\n";
   return 0;
}

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