Submission #727764

#	Time	Username	Problem	Language	Result	Execution time	Memory
727764		SanguineChameleon	Duathlon (APIO18_duathlon)	C++17	100 / 100	118 ms	47564 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 2e5 + 20;
bool flag[maxn];
int high[maxn];
int depth[maxn];
int cnt[maxn];
int cnt_sum1[maxn];
long long cnt_sum2[maxn];
bool art[maxn];
vector<int> adj[maxn];
vector<int> adj_tree[maxn];
vector<int> ch[maxn];
long long res;
int color_cnt;

void dfs1(int u, int par) {
	flag[u] = true;
	high[u] = depth[u];
	for (auto v: adj[u]) {
		if (v == par) {
			continue;
		}
		if (!flag[v]) {
			depth[v] = depth[u] + 1;
			ch[u].push_back(v);
			dfs1(v, u);
			high[u] = min(high[u], high[v]);
		}
		else {
			high[u] = min(high[u], depth[v]);
		}
	}
}

void dfs2(int u, int cur_color, bool root = false) {
	for (auto v: ch[u]) {
		if (high[v] >= depth[u] && (!root || (int)ch[u].size() >= 2)) {
			art[u] = true;
			color_cnt++;
			adj_tree[u].push_back(color_cnt);
			adj_tree[color_cnt].push_back(u);
			dfs2(v, color_cnt);
		}
		else {
			dfs2(v, cur_color);
		}
	}
	if (art[u]) {
		adj_tree[u].push_back(cur_color);
		adj_tree[cur_color].push_back(u);
	}
	else {
		cnt[cur_color]++;
	}
}

void dfs3(int u, int par) {
	cnt_sum1[u] = cnt[u];
	cnt_sum2[u] = 0;
	for (auto v: adj_tree[u]) {
		if (v != par) {
			dfs3(v, u);
			cnt_sum1[u] += cnt_sum1[v];
			cnt_sum2[u] += 1LL * cnt_sum1[v] * cnt_sum1[v];
		}
	}
}

long long ways1(int u) {
	return 1LL * cnt_sum1[u] * cnt_sum1[u] - cnt_sum2[u] - 1LL * cnt[u] * cnt[u] - 1LL * cnt[u] * (cnt_sum1[u] - cnt[u]) * 2;
}

long long ways2(int u) {
	return 1LL * cnt_sum1[u] * cnt_sum1[u] - cnt_sum2[u] - cnt[u];
}

void dfs4(int u, int par) {
	if (art[u]) {
		res += ways1(u);
		for (auto v: adj_tree[u]) {
			res += ways2(v);
		}
	}
	else {
		res += 1LL * cnt[u] * ways1(u);
		res += 1LL * cnt[u] * (cnt[u] - 1) * (cnt_sum1[u] - cnt[u]) * 2;
		res += 1LL * cnt[u] * (cnt[u] - 1) * (cnt[u] - 2);
	}
	for (auto v: adj_tree[u]) {
		if (v != par) {
			cnt_sum1[u] -= cnt_sum1[v];
			cnt_sum2[u] -= 1LL * cnt_sum1[v] * cnt_sum1[v];
			cnt_sum1[v] += cnt_sum1[u];
			cnt_sum2[v] += 1LL * cnt_sum1[u] * cnt_sum1[u];
			dfs4(v, u);
			cnt_sum1[v] -= cnt_sum1[u];
			cnt_sum2[v] -= 1LL * cnt_sum1[u] * cnt_sum1[u];
			cnt_sum1[u] += cnt_sum1[v];
			cnt_sum2[u] += 1LL * cnt_sum1[v] * cnt_sum1[v];
		}
	}
}

void solve(int root) {
	dfs1(root, -1);
	dfs2(root, ++color_cnt, true);
	dfs3(color_cnt, -1);
	dfs4(color_cnt, -1);
}

void just_do_it() {
	int n, m;
	cin >> n >> m;
	color_cnt = n;
	for (int i = 1; i <= n; i++) {
		cnt[i] = 1;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!flag[i]) {
			solve(i);
		}
	}
	cout << res;
}

• 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