Submission #797328

#	Time	Username	Problem	Language	Result	Execution time	Memory
797328		radaiosm7	Duathlon (APIO18_duathlon)	C++98	23 / 100	1073 ms	1048576 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;
vector<int> adj[100005];
bool visited[100005];
long long sub[100005];

void dfs1(int x, int p=-1) {
  visited[x] = true;
  sub[x] = 1LL;
  ++cc;

  for (auto y : adj[x]) {
    if (y == p) continue;
    dfs1(y, x);
    sub[x] += sub[y]; 
  }
}

void dfs2(int x, int p=-1) {
  ans += 2LL*(sub[x]-1LL)*(cc-sub[x]);

  for (auto y : adj[x]) {
    if (y == p) continue;
    ans += sub[y]*(sub[x]-1LL-sub[y]);
    dfs2(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]) {
      cc = 0LL;
      dfs1(i);
      dfs2(i);
    }
  }

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

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10