oj.uz

Submission #797323

# Submission time Handle Problem Language Result Execution time Memory
797323 2023-07-29T09:15:54 Z radaiosm7 Duathlon (APIO18_duathlon) C++
0 / 100
 869 ms 1048576 KB 
#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 += 2LL*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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 447 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 447 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 869 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

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 43 ms 6860 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 33 ms 6664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 447 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 447 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -