oj.uz

Submission #370785

# Submission time Handle Problem Language Result Execution time Memory
370785 2021-02-24T15:33:26 Z luciocf Duathlon (APIO18_duathlon) C++14
0 / 100
 131 ms 33824 KB 
#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;

	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*sz[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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 9 ms 14572 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 9 ms 14572 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 33136 KB Output is correct
2 Correct 90 ms 33136 KB Output is correct
3 Incorrect 117 ms 33824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 31628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 31772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 9 ms 14572 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 9 ms 14572 KB Output is correct
3 Correct 9 ms 14444 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 9 ms 14444 KB Output is correct
7 Incorrect 9 ms 14444 KB Output isn't correct
8 Halted 0 ms 0 KB -