Submission #370788

#	Time	Username	Problem	Language	Result	Execution time	Memory
370788		luciocf	Duathlon (APIO18_duathlon)	C++14	31 / 100	143 ms	41376 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 3e5+10;

int n;
int in[maxn], low[maxn], id[maxn], tt, cc;

bool is[maxn];

int sz[maxn], sub[maxn];
int comp_tree[maxn], sz_comp[maxn];

bool solved[maxn];

vector<int> grafo[maxn], tree[maxn], stk;

vector<vector<int>> comp;

void dfs(int u, int p)
{
	in[u] = low[u] = ++tt;
	stk.push_back(u);

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		if (in[v]) low[u] = min(low[u], in[v]);
		else
		{
			dfs(v, u);

			low[u] = min(low[u], low[v]);

			if (low[v] >= in[u])
			{
				is[u] = (in[u] > 1 || in[v] > 2);

				comp.push_back({u});

				while (stk.back() != u)
				{
					comp.back().push_back(stk.back());
					stk.pop_back();
				}
			}
		}
	}
}

void build(void)
{
	for (int i = 1; i <= n; i++)
	{
		if (is[i])
		{
			id[i] = ++cc;
			sz[cc]++;
		}
	}


	for (auto &C: comp)
	{	
		cc++;

		for (auto u: C)
		{
			if (!is[u])
			{
				id[u] = cc;
				sz[cc]++;
			}
			else
			{
				tree[id[u]].push_back(cc);
				tree[cc].push_back(id[u]);
			}
		}
	}
}

ll ans;

ll choose2(int n)
{
	return 1ll*n*(n-1)/2ll;
}

ll choose3(int n)
{
	return 1ll*n*(n-1)*(n-2)/6ll;
}

void calc(int u, int p, int cc)
{
	comp_tree[u] = cc;
	sz_comp[cc] += sz[u];

	sub[u] = sz[u];

	for (auto v: tree[u])
	{
		if (v == p) continue;

		calc(v, u, cc);

		sub[u] += sub[v];
	}
}

void solve(int u, int p)
{
	solved[comp_tree[u]] = 1;

	ans += 2ll*choose2(sz[p])*sz[u];
	if (sz[u] >= 3) ans += 6ll*choose3(sz[u]);
	if (sz[u] >= 2) ans += 4ll*choose2(sz[u])*(sub[u]-sz[u] + sz_comp[comp_tree[u]]-sub[u]);

	ans += 2ll*sz[u]*(sz_comp[comp_tree[u]]-sub[u])*(sub[u]-sz[u]);

	int soma = 0;

	for (auto v: tree[u])
	{
		if (v == p) continue;

		ans += 2ll*sz[u]*soma*sub[v];
		soma += sub[v];

		ans += 2ll*choose2(sz[v])*sz[u];

		solve(v, u);
	}
}

int main(void)
{
	int m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
		if (!in[i])
			dfs(i, 0);

	build();

	int cc_tree = 0;

	for (int i = 1; i <= 2*n; i++)
		if (!comp_tree[i])
			calc(i, 0, ++cc_tree);

	for (int i = 1; i <= 2*n; i++)
		if (!solved[comp_tree[i]])
			solve(i, 0);

	printf("%lld\n", ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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