Submission #111241

#	Time	Username	Problem	Language	Result	Execution time	Memory
111241		diamond_duke	Duathlon (APIO18_duathlon)	C++11	100 / 100	168 ms	25376 KiB

count_triplets

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using ll = long long;
int lst[100005], to[400005], pre[400005], tot;
int low[100005], dfn[100005], st[100005], clk, tp;
int sz[200005], n, m, t_cnt;
std::vector<int> son[200005];
ll ans;
inline void add_edge(int u, int v)
{
	to[tot] = v;
	pre[tot] = lst[u];
	lst[u] = tot++;
}
void tarjan(int u, int fa = -1)
{
	dfn[u] = low[u] = clk++;
	st[tp++] = u;
	for (int i = lst[u]; ~i; i = pre[i])
	{
		int v = to[i];
		if (-1 == dfn[v])
		{
			tarjan(v, i ^ 1);
			low[u] = std::min(low[u], low[v]);
			if (low[v] >= dfn[u])
			{
				son[u].push_back(t_cnt);
				do
					son[t_cnt].push_back(st[--tp]);
				while (st[tp] != v);
				t_cnt++;
			}
		}
		else if (i != fa)
			low[u] = std::min(low[u], dfn[v]);
	}
}
void dfs(int u)
{
	sz[u] = u < n;
	for (int v : son[u])
	{
		dfs(v);
		sz[u] += sz[v];
	}
}
void work(int u, int rt, int fa = -1)
{
	for (int v : son[u])
	{
		if (u < n)
			ans += (ll)sz[v] * (sz[rt] - sz[v] - 1);
		else
			ans += (ll)sz[v] * (sz[rt] - sz[v]) * (son[u].size() - 1);
		work(v, rt, u);
	}
	if (~fa)
	{
		if (u < n)
			ans += (ll)(sz[rt] - sz[u]) * (sz[u] - 1);
		else
			ans += (ll)(sz[rt] - sz[u]) * sz[u] * (son[u].size() - 1);
	}
}
int main()
{
	// freopen("uoj-416.in", "r", stdin);
	memset(lst, -1, sizeof(lst));
	memset(dfn, -1, sizeof(dfn));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(--u, --v);
		add_edge(v, u);
	}
	t_cnt = n;
	for (int i = 0; i < n; i++)
	{
		if (-1 == dfn[i])
		{
			tarjan(i);
			dfs(i);
			work(i, i);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• 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