oj.uz

Submission #405537

# Submission time Handle Problem Language Result Execution time Memory
405537 2021-05-16T14:11:26 Z BERNARB01 Duathlon (APIO18_duathlon) C++17
31 / 100
 211 ms 29048 KB 
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class graph {
  public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector< vector<int> > g;
  int n;

  function<bool(int)> ignore;

  graph(int _n) : n(_n) {
    g.resize(n);
    ignore = nullptr;
  }

  virtual int add(int from, int to, T cost) = 0;

  virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
    ignore = f;
  }

  virtual void reset_ignore_edge_rule() {
    ignore = nullptr;
  }
};

template <typename T>
class undigraph : public graph<T> {
  public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  undigraph(int _n) : graph<T>(_n) {
  }

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

template <typename T>
class dfs_undigraph : public undigraph<T> {
  public:
  using undigraph<T>::edges;
  using undigraph<T>::g;
  using undigraph<T>::n;
  using undigraph<T>::ignore;

  vector<int> pv;
  vector<int> pe;
  vector<int> order;
  vector<int> pos;
  vector<int> end;
  vector<int> sz;
  vector<int> root;
  vector<int> depth;
  vector<int> min_depth;
  vector<T> dist;
  vector<int> was;
  int attempt;

  dfs_undigraph(int _n) : undigraph<T>(_n) {
  }

  void init() {
    pv = vector<int>(n, -1);
    pe = vector<int>(n, -1);
    order.clear();
    pos = vector<int>(n, -1);
    end = vector<int>(n, -1);
    sz = vector<int>(n, 0);
    root = vector<int>(n, -1);
    depth = vector<int>(n, -1);
    min_depth = vector<int>(n, -1);
    dist = vector<T>(n);
    was = vector<int>(n, -1);
    attempt = 0;
  }

  void clear() {
    pv.clear();
    pe.clear();
    order.clear();
    pos.clear();
    end.clear();
    sz.clear();
    root.clear();
    depth.clear();
    min_depth.clear();
    dist.clear();
    was.clear();
  }

  private:
  void do_dfs(int v) {
    was[v] = attempt;
    pos[v] = (int) order.size();
    order.push_back(v);
    sz[v] = 1;
    min_depth[v] = depth[v];
    for (int id : g[v]) {
      if (id == pe[v] || (ignore != nullptr && ignore(id))) {
        continue;
      }
      auto &e = edges[id];
      int to = e.from ^ e.to ^ v;
      if (was[to] == attempt) {
        min_depth[v] = min(min_depth[v], depth[to]);
        continue;
      }
      depth[to] = depth[v] + 1;
      dist[to] = dist[v] + e.cost;
      pv[to] = v;
      pe[to] = id;
      root[to] = (root[v] != -1 ? root[v] : to);
      do_dfs(to);
      sz[v] += sz[to];
      min_depth[v] = min(min_depth[v], min_depth[to]);
    }
    end[v] = (int) order.size() - 1;
  }

  void do_dfs_from(int v) {
    ++attempt;
    depth[v] = 0;
    dist[v] = T{};
    root[v] = v;
    pv[v] = pe[v] = -1;
    do_dfs(v);
  }

  public:
  void dfs(int v, bool clear_order = true) {
    if (pv.empty()) {
      init();
    } else {
      if (clear_order) {
        order.clear();
      }
    }
    do_dfs_from(v);
  }

  void dfs_all() {
    init();
    for (int v = 0; v < n; v++) {
      if (depth[v] == -1) {
        do_dfs_from(v);
      }
    }
    assert((int) order.size() == n);
  }
};

template <typename T>
vector<int> find_bicone(dfs_undigraph<T> &g, int &cnt) {
  g.dfs_all();
  vector<int> vertex_comp(g.n);
  cnt = 0;
  for (int i : g.order) {
    if (g.pv[i] == -1 || g.min_depth[i] == g.depth[i]) {
      vertex_comp[i] = cnt++;
    } else {
      vertex_comp[i] = vertex_comp[g.pv[i]];
    }
  }
  return vertex_comp;
}

struct dsu {
	int nCC;
	vector<int> pr, sz, rank;
	dsu(int n) {
		nCC = n;
		pr.resize(n);
		sz.assign(n, 1);
		rank.assign(n, 1);
		iota(pr.begin(), pr.end(), 0);
	}
	int fnd(int u) {
		if (u == pr[u]) {
			return u;
		}
		pr[u] = fnd(pr[u]);
		return pr[u];
	}
	bool unate(int u, int v) {
		u = fnd(u); v = fnd(v);
		if (u == v) {
			return false;
		}
		--nCC;
		if (rank[u] > rank[v]) {
			swap(u, v);
		}
		pr[u] = v;
		rank[v] += (rank[u] == rank[v]);
		sz[v] += sz[u];
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	dfs_undigraph<int> gg(n);
	dsu se(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		gg.add(u, v);
		se.unate(u, v);
	}
	int cnt;
	vector<int> comp = find_bicone(gg, cnt);
	vector<int> a(cnt, 0);
	vector<int> dsu_par(cnt);
	for (int i = 0; i < n; i++) {
		a[comp[i]]++;
		dsu_par[comp[i]] = i;
	}
	dsu se2(n);
	for (int i = 0; i < n; i++) {
		se2.unate(i, dsu_par[comp[i]]);
	}
	vector<vector<int>> g(cnt);
	vector<int> deg(cnt, 0);
	for (auto e : gg.edges) {
		if (se2.unate(e.from, e.to)) {
			g[comp[e.from]].push_back(comp[e.to]);
			g[comp[e.to]].push_back(comp[e.from]);
			deg[comp[e.from]]++;
			deg[comp[e.to]]++;
		}
	}
	long long ans = 0;
	for (int i = 0; i < cnt; i++) {
		dsu_par[i] = se.fnd(dsu_par[i]);
		if (a[i] > 2) {
			ans += a[i] * 1LL * (a[i] - 1) * (a[i] - 2);
		}
		if (a[i] > 1) {
			ans += (a[i] - deg[i]) * 2LL * (a[i] - 1) * (se.sz[dsu_par[i]] - a[i]);
		}
	}
	vector<long long> sbt(cnt, 0);
	function<int(int, int)> dfs0 = [&](int u, int p) {
		int r = 1;
		sbt[u] = a[u];
		for (int v : g[u]) {
			if (v != p) {
				r += dfs0(v, u);
				sbt[u] += sbt[v];
			}
		}
		return r;
	};
	function<void(int, int, int)> DFS = [&](int u, int p, int nn) {
		for (int v : g[u]) {
			if (v != p) {
				DFS(v, u, nn);
			}
		}
		long long sum = nn - 1;
		long long sbtp = nn - sbt[u];
		ans += sbtp * 1LL * (sum - sbtp);
		for (int v : g[u]) {
			if (v != p) {
				ans += sbt[v] * 1LL * (sum - sbt[v]);
			}
		}
	};
	for (int i = 0; i < cnt; i++) {
		if (sbt[i] == 0) {
			int sz = dfs0(i, -1);
			if (sz > 2) {
				DFS(i, -1, sz);
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 23448 KB Output is correct
2 Correct 102 ms 23460 KB Output is correct
3 Correct 114 ms 22816 KB Output is correct
4 Correct 110 ms 22864 KB Output is correct
5 Correct 113 ms 19700 KB Output is correct
6 Correct 142 ms 22296 KB Output is correct
7 Correct 116 ms 20800 KB Output is correct
8 Correct 125 ms 21244 KB Output is correct
9 Correct 134 ms 19708 KB Output is correct
10 Correct 144 ms 19576 KB Output is correct
11 Correct 91 ms 18176 KB Output is correct
12 Correct 121 ms 18192 KB Output is correct
13 Correct 113 ms 18424 KB Output is correct
14 Correct 96 ms 18176 KB Output is correct
15 Correct 70 ms 18408 KB Output is correct
16 Correct 88 ms 17956 KB Output is correct
17 Correct 16 ms 14108 KB Output is correct
18 Correct 17 ms 14084 KB Output is correct
19 Correct 15 ms 14096 KB Output is correct
20 Correct 16 ms 14152 KB Output is correct
21 Correct 15 ms 14156 KB Output is correct
22 Correct 15 ms 14156 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 21572 KB Output is correct
2 Correct 154 ms 22484 KB Output is correct
3 Correct 139 ms 22544 KB Output is correct
4 Correct 167 ms 22556 KB Output is correct
5 Correct 174 ms 22444 KB Output is correct
6 Correct 163 ms 29048 KB Output is correct
7 Correct 181 ms 26792 KB Output is correct
8 Correct 211 ms 25728 KB Output is correct
9 Correct 154 ms 24592 KB Output is correct
10 Correct 142 ms 22520 KB Output is correct
11 Correct 159 ms 22036 KB Output is correct
12 Correct 127 ms 22024 KB Output is correct
13 Correct 155 ms 21948 KB Output is correct
14 Correct 119 ms 21668 KB Output is correct
15 Correct 136 ms 21368 KB Output is correct
16 Correct 80 ms 19628 KB Output is correct
17 Correct 87 ms 22708 KB Output is correct
18 Correct 97 ms 22664 KB Output is correct
19 Correct 87 ms 22872 KB Output is correct
20 Correct 107 ms 22800 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 21708 KB Output is correct
2 Correct 147 ms 22188 KB Output is correct
3 Incorrect 131 ms 20728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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