oj.uz

Submission #265287

# Submission time Handle Problem Language Result Execution time Memory
265287 2020-08-14T14:51:42 Z extraterrestrial Duathlon (APIO18_duathlon) C++14
36 / 100
 493 ms 16816 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], have_cycle;
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];
    }
    else if (u != pr[v]) {
      have_cycle = true;
    }
  }
}

int sum = 0;
vector<int> path;
bool was[11][11][11];
void go(int mask) {
  int cnt = __builtin_popcount(mask);
  if (cnt >= 3) {
    for (int i = 1; i + 1 < SZ(path); i++) {
      if (!was[path[0]][path[i]][path.back()]) {
        was[path[0]][path[i]][path.back()] = true;
        sum++;
      }
    }
  }
  for (auto u : g[path.back()]) {
    if ((mask >> u) & 1) {
      continue;
    }
    path.pb(u);
    go(mask | (1 << u));
    path.pop_back();
  }
}

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 * sz[i]) {
          ans += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2);
        }
        else {
          assert(sum_sz == 2 * (sz[i] - 1));
          ans += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2) / 3;
        }
      }
    }
    cout << ans << '\n';
    exit(0);
  }
  if (n <= 10) {
    for (int i = 1; i <= n; i++) {
      path.pb(i);
      go(1 << i);
      path.pop_back();
      //cout << sum << '\n';
    }
    cout << sum << '\n';
    exit(0);
  }
  for (int i = 1; i <= n; i++) {
    if (!used[i]) {
      dfs(i, i);
    }
  }
  if (!have_cycle) {
    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';
  }
  else {
    assert(false);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 19 ms 2688 KB Output is correct
10 Correct 493 ms 2736 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 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 3 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 3 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 19 ms 2688 KB Output is correct
10 Correct 493 ms 2736 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 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 3 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 3 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct
36 Correct 2 ms 2688 KB Output is correct
37 Correct 2 ms 2688 KB Output is correct
38 Runtime error 6 ms 5248 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15148 KB Output is correct
2 Correct 68 ms 15088 KB Output is correct
3 Correct 73 ms 11844 KB Output is correct
4 Correct 74 ms 13552 KB Output is correct
5 Correct 66 ms 10744 KB Output is correct
6 Correct 65 ms 10744 KB Output is correct
7 Correct 62 ms 9848 KB Output is correct
8 Correct 62 ms 10356 KB Output is correct
9 Correct 66 ms 9208 KB Output is correct
10 Correct 60 ms 9720 KB Output is correct
11 Correct 57 ms 8128 KB Output is correct
12 Correct 46 ms 7928 KB Output is correct
13 Correct 43 ms 7928 KB Output is correct
14 Correct 51 ms 7800 KB Output is correct
15 Correct 32 ms 7164 KB Output is correct
16 Correct 32 ms 7160 KB Output is correct
17 Correct 5 ms 3840 KB Output is correct
18 Correct 4 ms 3840 KB Output is correct
19 Correct 4 ms 3840 KB Output is correct
20 Correct 4 ms 3840 KB Output is correct
21 Correct 4 ms 3840 KB Output is correct
22 Correct 6 ms 3840 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 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 2848 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 2 ms 2816 KB Output is correct
12 Correct 2 ms 2720 KB Output is correct
13 Correct 2 ms 2816 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2816 KB Output is correct
17 Correct 2 ms 2816 KB Output is correct
18 Correct 2 ms 2816 KB Output is correct
19 Correct 2 ms 2816 KB Output is correct
20 Correct 2 ms 2816 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9164 KB Output is correct
2 Correct 69 ms 9076 KB Output is correct
3 Correct 78 ms 9076 KB Output is correct
4 Correct 75 ms 9076 KB Output is correct
5 Correct 69 ms 9188 KB Output is correct
6 Correct 71 ms 12404 KB Output is correct
7 Correct 72 ms 11120 KB Output is correct
8 Correct 65 ms 10608 KB Output is correct
9 Correct 62 ms 10100 KB Output is correct
10 Correct 78 ms 9332 KB Output is correct
11 Correct 60 ms 9076 KB Output is correct
12 Correct 63 ms 9276 KB Output is correct
13 Correct 64 ms 9076 KB Output is correct
14 Correct 56 ms 8824 KB Output is correct
15 Correct 56 ms 8604 KB Output is correct
16 Correct 33 ms 7544 KB Output is correct
17 Correct 49 ms 9456 KB Output is correct
18 Correct 41 ms 9328 KB Output is correct
19 Correct 37 ms 9324 KB Output is correct
20 Correct 39 ms 9332 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 Runtime error 6 ms 5376 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9076 KB Output is correct
2 Correct 69 ms 9080 KB Output is correct
3 Runtime error 91 ms 16816 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 19 ms 2688 KB Output is correct
10 Correct 493 ms 2736 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 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 3 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 3 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct
36 Correct 2 ms 2688 KB Output is correct
37 Correct 2 ms 2688 KB Output is correct
38 Runtime error 6 ms 5248 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 19 ms 2688 KB Output is correct
10 Correct 493 ms 2736 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 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 3 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 3 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct
36 Correct 2 ms 2688 KB Output is correct
37 Correct 2 ms 2688 KB Output is correct
38 Runtime error 6 ms 5248 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -