oj.uz

Submission #255453

# Submission time Handle Problem Language Result Execution time Memory
255453 2020-08-01T04:33:35 Z EntityIT Duathlon (APIO18_duathlon) C++14
0 / 100
 183 ms 30288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_vertices, n_edges; cin >> n_vertices >> n_edges;
  vec<int, 2> neighbors_vertices(n_vertices);
  while (n_edges--) {
    int u, v; cin >> u >> v; --u; --v;
    neighbors_vertices[u].emplace_back(v);
    neighbors_vertices[v].emplace_back(u);
  }

  vec<int, 1> parents(n_vertices, -1), discoveries(n_vertices, -1), earliests(n_vertices, -1);
  int n_vertices_block_cut_tree = n_vertices;
  vec<int, 2> neighbors_vertices_block_cut_tree(n_vertices);
  function<void(int)> ConstructBlockCutTree = [&](int u) {
    static int current_discovery = -1;
    static stack<pair<int, int>> current_edges;

    discoveries[u] = earliests[u] = ++current_discovery;
    for (auto& v : neighbors_vertices[u]) {
      if (!~discoveries[v]) {
        parents[v] = u;
        current_edges.emplace(u, v);
        ConstructBlockCutTree(v);
        Minimize(earliests[u], earliests[v]);

        if (earliests[v] >= discoveries[u]) {
          vec<int, 1> vertices;
          do {
            vertices.emplace_back(current_edges.top().first);
            vertices.emplace_back(current_edges.top().second);
            current_edges.pop();
          } while (vertices.rbegin()[1] != u || vertices.back() != v);
          sort(ALL(vertices)); vertices.erase(unique(ALL(vertices)), vertices.end());
          neighbors_vertices_block_cut_tree.emplace_back(vec<int, 1>());
          for (auto& vertex : vertices) {
            neighbors_vertices_block_cut_tree[vertex].emplace_back(n_vertices_block_cut_tree);
            neighbors_vertices_block_cut_tree[n_vertices_block_cut_tree].emplace_back(vertex);
          }
          ++n_vertices_block_cut_tree;
        }
      } else if (v != parents[u] && discoveries[v] < discoveries[u]) {
        current_edges.emplace(u, v);
        Minimize(earliests[u], discoveries[v]);
      }
    }
  };
  for (int u = 0; u < n_vertices; ++u) {
    if (!~discoveries[u]) {
      ConstructBlockCutTree(u);
    }
  }

  int64_t answer = static_cast<int64_t>(n_vertices) * (n_vertices - 1) * (n_vertices - 2);
  vec<int, 1> a(n_vertices_block_cut_tree);
  function<int(int, int)> Solve = [&](int u, int parent) {
    a[u] = (u < n_vertices);
    for (auto& v : neighbors_vertices_block_cut_tree[u]) {
      if (v == parent) {
        continue;
      }
      a[u] += Solve(v, u);
      if (u >= n_vertices) {
        answer -= static_cast<int64_t>(SZ(neighbors_vertices_block_cut_tree[u]) - 1) * a[v] * (a[v] - 1);
      }
    }
    if (u >= n_vertices) {
      answer -= static_cast<int64_t>(SZ(neighbors_vertices_block_cut_tree[u]) - 1) * (n_vertices - a[u]) * ((n_vertices - a[u]) - 1);
    }
    return a[u];
  };
  Solve(0, -1);

  cout << answer << '\n';

  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 29040 KB Output is correct
2 Correct 121 ms 29112 KB Output is correct
3 Incorrect 147 ms 24428 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Incorrect 2 ms 512 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 20176 KB Output is correct
2 Correct 129 ms 20176 KB Output is correct
3 Correct 155 ms 20236 KB Output is correct
4 Correct 127 ms 20176 KB Output is correct
5 Correct 124 ms 20176 KB Output is correct
6 Correct 139 ms 30288 KB Output is correct
7 Correct 139 ms 26832 KB Output is correct
8 Correct 167 ms 25092 KB Output is correct
9 Correct 165 ms 23376 KB Output is correct
10 Incorrect 148 ms 20176 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Incorrect 1 ms 512 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 20180 KB Output is correct
2 Correct 128 ms 20176 KB Output is correct
3 Correct 134 ms 19280 KB Output is correct
4 Correct 132 ms 18128 KB Output is correct
5 Correct 176 ms 16720 KB Output is correct
6 Correct 131 ms 16208 KB Output is correct
7 Correct 115 ms 15824 KB Output is correct
8 Correct 157 ms 15440 KB Output is correct
9 Correct 157 ms 15440 KB Output is correct
10 Correct 111 ms 15368 KB Output is correct
11 Correct 153 ms 15184 KB Output is correct
12 Correct 146 ms 15180 KB Output is correct
13 Correct 158 ms 15312 KB Output is correct
14 Correct 153 ms 18432 KB Output is correct
15 Correct 159 ms 26576 KB Output is correct
16 Correct 143 ms 24016 KB Output is correct
17 Correct 140 ms 24656 KB Output is correct
18 Correct 183 ms 22548 KB Output is correct
19 Incorrect 131 ms 18108 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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