Submission #797295

#	Time	Username	Problem	Language	Result	Execution time	Memory
797295		radaiosm7	Duathlon (APIO18_duathlon)	C++98	8 / 100	41 ms	11792 KiB

count_triplets

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10