oj.uz

Submission #265136

# Submission time Handle Problem Language Result Execution time Memory
265136 2020-08-14T13:21:50 Z extraterrestrial Duathlon (APIO18_duathlon) C++14
23 / 100
 105 ms 21108 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll    

const int N = 1e5 + 10;
vector<int> g[N], comp;
bool used[N];
int sz[N], root[N], pr[N];

void dfs(int v, int rt) {
  comp.pb(v);
  used[v] = true;
  sz[v] = 1;
  root[v] = rt;
  for (auto u : g[v]) {
    if (!used[u]) {
      pr[u] = v;
      dfs(u, rt);
      sz[v] += sz[u];
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  bool gr2 = true;
  for (int i = 1; i <= n; i++) {
    if (SZ(g[i]) > 2) {
      gr2 = false;
      break;
    }
  }
  if (gr2) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      if (!used[i]) {
        comp = {};
        dfs(i, i);
        int sum_sz = 0;
        for (int v : comp) {
          sum_sz += SZ(g[v]);
        } 
        if (sum_sz == 2 * n) {
          ans += 1ll * n * (n - 1) * (n - 2);
        }
        else {
          assert(sum_sz == 2 * (n - 1));
          ans += 1ll * n * (n - 1) * (n - 2) / 3;
        }
      }
    }
    cout << ans << '\n';
    exit(0);
  }
  for (int i = 1; i <= n; i++) {
    if (!used[i]) {
      dfs(i, i);
    }
  }
  ll ans = 0;
  for (int v = 1; v <= n; v++) {
    for (auto u : g[v]) {
      if (u == pr[v]) {
        ans += (sz[root[v]] - sz[v]) * 1ll * (sz[v] - 1);
      }
      else {
        ans += sz[u] * 1ll * (sz[root[v]] - sz[u] - 1);
      }
    }
  }
  cout << ans << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13808 KB Output is correct
2 Correct 80 ms 13800 KB Output is correct
3 Runtime error 85 ms 21108 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2944 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct
10 Correct 3 ms 2688 KB Output is correct
11 Correct 2 ms 2816 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 3 ms 2816 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7880 KB Output is correct
2 Correct 75 ms 7796 KB Output is correct
3 Correct 92 ms 7848 KB Output is correct
4 Correct 56 ms 7796 KB Output is correct
5 Correct 72 ms 7796 KB Output is correct
6 Correct 83 ms 11252 KB Output is correct
7 Correct 91 ms 9840 KB Output is correct
8 Correct 95 ms 9268 KB Output is correct
9 Correct 78 ms 8900 KB Output is correct
10 Correct 96 ms 7796 KB Output is correct
11 Correct 99 ms 7796 KB Output is correct
12 Correct 92 ms 7800 KB Output is correct
13 Correct 100 ms 7800 KB Output is correct
14 Correct 95 ms 7800 KB Output is correct
15 Correct 82 ms 7672 KB Output is correct
16 Correct 54 ms 6940 KB Output is correct
17 Correct 52 ms 8304 KB Output is correct
18 Correct 64 ms 8176 KB Output is correct
19 Correct 58 ms 8172 KB Output is correct
20 Correct 60 ms 8180 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7780 KB Output is correct
2 Correct 72 ms 7752 KB Output is correct
3 Incorrect 105 ms 7752 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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