답안 #255453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255453	2020-08-01T04:33:35 Z	EntityIT	철인 이종 경기 (APIO18_duathlon)	C++14	0 / 100	183 ms	30288 KB

count_triplets

#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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #255453

Compilation message