Submission #566654

#	Time	Username	Problem	Language	Result	Execution time	Memory
566654		Drew_	Duathlon (APIO18_duathlon)	C++17	100 / 100	115 ms	28200 KiB

count_triplets

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

#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 1e5 + 7;
static ll ans = 0;

int N, M;
vector<int> adj[MAX]; //[from]: to

// bct
int ctr_node, bcc = 0;
int sz[2*MAX];
vector<int> tree[2*MAX];

// solve
int cur_ctr = 0;
int disc[MAX], low[MAX];
vector<int> sk;
void build_bct(int node, int par)	
{
	disc[node] = low[node] = cur_ctr++;
	sk.pb(node);

	ctr_node++;
	for (int to : adj[node]) if (to != par)
	{
		if (disc[to] == -1)
		{
			build_bct(to, node);
			low[node] = min(low[node], low[to]);

			if (low[to] >= disc[node])
			{
				bcc++;
				tree[node].pb(N + bcc);
				while (tree[N + bcc].empty() || tree[N + bcc].back() != to)
					tree[N + bcc].pb(sk.back()), sk.pop_back();
			}
		}
		else low[node] = min(low[node], disc[to]);
	}
}

int dfs(int node)
{
	sz[node] = node <= N;
	for (int to : tree[node])
	{
		sz[node] += dfs(to);
		if (node > N)
			ans -= 1ll * (int)tree[node].size() * sz[to] * (sz[to] - 1);
	}
	if (node > N)
		ans -= 1ll * (int)tree[node].size() * (ctr_node - sz[node]) * (ctr_node - sz[node] - 1);

	return sz[node];
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	for (int u, v; M--;)
	{
		cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}

	memset(disc, -1, sizeof(disc));
	for (int i = 1; i <= N; ++i) if (disc[i] == -1)
	{
		ctr_node = 0;
		build_bct(i, -1);

		ans += 1ll * ctr_node * (ctr_node - 1) * (ctr_node - 2);
		dfs(i);
	}

	cout << ans << '\n';
	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