oj.uz

Submission #797295

# Submission time Handle Problem Language Result Execution time Memory
797295 2023-07-29T08:57:53 Z radaiosm7 Duathlon (APIO18_duathlon) C++
8 / 100
 41 ms 11792 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, m, i, a, b;
long long ans, cc, j;
vector<int> adj[100005];
bool visited[100005];
bool isCycle;

void dfs(int x, int p) {
  visited[x] = true;
  ++cc;

  for (auto y : adj[x]) {
    if (y == p) continue;
    if (visited[y]) isCycle = true;
    else dfs(y, x);
  }
}

int main() {
  scanf("%d%d", &n, &m);

  for (i=0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  ans = 0LL;
  fill(visited+1, visited+n+1, false);

  for (i=1; i <= n; ++i) {
    if (!visited[i]) {
      isCycle = false;
      cc = 0LL;
      dfs(i, -1);

      if (cc <= 2LL) continue;
      if (isCycle) ans += cc*(cc-1LL)*(cc-2LL);
      else for (j=2LL; j < cc; ++j) ans += 2LL*(j-1LL)*(cc-j);
    }
  }

  printf("%lld\n", ans);
  return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 11792 KB Output is correct
2 Correct 32 ms 11768 KB Output is correct
3 Correct 30 ms 9436 KB Output is correct
4 Correct 32 ms 10604 KB Output is correct
5 Correct 30 ms 8652 KB Output is correct
6 Correct 30 ms 8656 KB Output is correct
7 Correct 34 ms 8012 KB Output is correct
8 Correct 30 ms 8320 KB Output is correct
9 Correct 29 ms 7472 KB Output is correct
10 Correct 31 ms 8012 KB Output is correct
11 Correct 39 ms 6980 KB Output is correct
12 Correct 25 ms 6688 KB Output is correct
13 Correct 27 ms 6668 KB Output is correct
14 Correct 23 ms 6456 KB Output is correct
15 Correct 19 ms 5992 KB Output is correct
16 Correct 17 ms 5824 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2656 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2664 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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