Submission #1163931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163931		Error42	Duathlon (APIO18_duathlon)	C++20	0 / 100	75 ms	45248 KiB

count_triplets

// TODO: input may be unconnected

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

using ll = long long;

namespace orig {
	vector<vector<int>> graph;

	vector<int> tm;
	vector<int> l;
	
	int cur_tm = 0;

	vector<vector<int>> components;
	vector<bool> articulation;
	stack<int> s;

	void dfs(int const cur, int const par) {
		l[cur] = tm[cur] = cur_tm;
		cur_tm++;
		s.push(cur);

		for (int const& neigh : graph[cur]) {
			if (neigh == par)
				continue;

			if (tm[neigh] == -1) {
				dfs(neigh, cur);

				if (l[neigh] >= tm[cur]) {
					components.push_back({ cur });
					articulation[cur] = cur != 0 || (cur == 0 && neigh != graph[0][0]);

					while (s.top() != cur) {
						components.back().push_back(s.top());
						s.pop();
					}
				}
			}

			l[cur] = min(l[cur], l[neigh]);
		}
	}
}

namespace bct {
	vector<vector<int>> graph;
	vector<ll> sz;
	vector<int> from_orig;

	ll ans = 0;
	vector<ll> subtree_sz;

	void dfs(int const cur, int const par) {
		subtree_sz[cur] = sz[cur];

		for (int const& neigh : graph[cur]) {
			if (neigh == par)
				continue;

			dfs(neigh, cur);
			subtree_sz[cur] += subtree_sz[neigh];
		}

		bool const articulation = cur >= orig::components.size();

		// s, f in node
		ans += sz[cur] * (sz[cur] - 1) * (sz[cur] - 2);

		if (!articulation)
			ans += graph[cur].size() * sz[cur] * (sz[cur] - 1);

		// s in node, f in strict subtree or vice verca
		ans += 2 * sz[cur] * (sz[cur] - 1) * (subtree_sz[cur] - sz[cur]);

		if (!articulation)
			ans += 2 * /* s: */ sz[cur] * /* f: */ (subtree_sz[cur] - sz[cur]) * /* c: */ ((ll)graph[cur].size() - 1);

		// s and f in different subtrees
		for (int const& neigh : graph[cur]) {
			if (neigh == par)
				continue;

			ans += sz[cur] * subtree_sz[neigh] * (subtree_sz[cur] - sz[cur] - subtree_sz[neigh]);

			if (!articulation)
				ans += /* s: */ subtree_sz[neigh] * /* f: */ (subtree_sz[cur] - sz[cur] - subtree_sz[neigh]) * /* c: */ ((ll)graph[cur].size() - 2);
		}

		// s in subtree, f not in subtree or vice verca
		ans += 2 * sz[cur] * (subtree_sz[cur] - 1) * ((ll)orig::graph.size() - subtree_sz[cur]);

		if (!articulation) {
			// s in node, f not in subtree or vice verca
			ans += 2 * /* s: */ sz[cur] * /* f: */ ((ll)orig::graph.size() - subtree_sz[cur]) * /* c: */ ((ll)graph[cur].size() - 1);
			// s in strict subtree, f not in subtree of vice verca
			ans += 2 * /* s: */ (subtree_sz[cur] - sz[cur]) * /* f: */ ((ll)orig::graph.size() - subtree_sz[cur]) * /* c: */ ((ll)graph[cur].size() - 2);
		}
	}
}

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

	int n, m;
	cin >> n >> m;
	
	orig::graph.assign(n, {});

	orig::tm.assign(n, -1);
	orig::l.assign(n, -1);
	orig::cur_tm = 0;

	orig::components.clear();
	orig::articulation.assign(n, false);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;

		orig::graph[u].push_back(v);
		orig::graph[v].push_back(u);
	}

	orig::dfs(0, -1);

	for (int i = 0; i < n; i++)
		if (orig::tm[i] == -1)
			return 1;

	bct::graph.assign(orig::components.size(), {});
	bct::from_orig.resize(n);
	
	for (int i = 0; i < n; i++) {
		if (orig::articulation[i]) {
			bct::from_orig[i] = bct::graph.size();
			bct::graph.push_back({});
		}
	}
	
	bct::sz.assign(bct::graph.size(), 0);
	fill(bct::sz.begin() + orig::components.size(), bct::sz.end(), 1);

	for (int component_i = 0; component_i < orig::components.size(); component_i++) {
		auto const& component = orig::components[component_i];

		for (int const& v : component) {
			if (orig::articulation[v]) {
				int const p = bct::from_orig[v];
				int const q = component_i;

				bct::graph[p].push_back(q);
				bct::graph[q].push_back(p);
			}
			else
				bct::sz[component_i]++;
		}
	}

	bct::subtree_sz.assign(bct::graph.size(), 0);

	bct::dfs(0, -1);

	cout << bct::ans << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10