oj.uz

Submission #156091

# Submission time Handle Problem Language Result Execution time Memory
156091 2019-10-03T08:52:11 Z IOrtroiii 우호 조약 체결 (JOI14_friends) C++14
0 / 100
 101 ms 6740 KB 
#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;
            merge(v, u);
            q.emplace(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3832 KB Output is correct
2 Incorrect 101 ms 6740 KB Output isn't correct
3 Halted 0 ms 0 KB -