Submission #453684

#	Time	Username	Problem	Language	Result	Execution time	Memory
453684		arminatarod	Duathlon (APIO18_duathlon)	C++17	100 / 100	148 ms	32192 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 200005;

constexpr int COMPONENT = 100002;

constexpr int MAXINT = 1073741823;

vector<long long int> neighbors[MAXN], links[MAXN];

bitset<MAXN> visited;

long long int answer, current_size, current_component;

long long int height[MAXN], minimum_height[MAXN], real_vertices[MAXN];

vector<int> current_vertices;

void dfs(int v, int level) {
	visited[v] = true;
	current_size++;
	height[v] = level;
	minimum_height[v] = height[v];
	current_vertices.push_back(v);
	for (int i : neighbors[v])
		if (visited[i])
			minimum_height[v] = min(minimum_height[v], height[i]);
		else {
			dfs(i, level + 1);
			minimum_height[v] = min(minimum_height[v], minimum_height[i]);
			if (minimum_height[i] >= height[v]) {
				links[v].push_back(COMPONENT + current_component);
				while (links[COMPONENT + current_component].empty() || links[COMPONENT + current_component].back() != i) {
					links[COMPONENT + current_component].push_back(current_vertices.back());
					current_vertices.pop_back();
				}
				current_component++;
			}
		}
	return;
}

void recheck(int v) {
	real_vertices[v] = (v < COMPONENT? 1 : 0);
	for (int i : links[v]) {
		recheck(i);
		real_vertices[v] += real_vertices[i];
		if (v >= COMPONENT)
			answer -= (long long int)links[v].size() * real_vertices[i] * (real_vertices[i] - 1LL);
	}
	if (v >= COMPONENT)
		answer -= (long long int)links[v].size() * (current_size - real_vertices[v]) * (current_size - real_vertices[v] - 1LL);
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, u, v;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		u--;
		v--;
		neighbors[u].push_back(v);
		neighbors[v].push_back(u);
	}
	for (int i = 0; i < n; i++)
		if (!visited[i]) {
			current_size = 0;
			dfs(i, 0);
			answer += current_size * (current_size - 1LL) * (current_size - 2LL);
			recheck(i);
		}
	cout << answer;
	return 0;
}

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