oj.uz

Submission #371442

# Submission time Handle Problem Language Result Execution time Memory
371442 2021-02-26T15:47:42 Z luciocf Duathlon (APIO18_duathlon) C++14
31 / 100
 188 ms 42652 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5+10;

int n;

pii edge[maxn];

int in[maxn], low[maxn], tt;
bool mark_edge[maxn], art[maxn];

int sz_bcc[maxn], sz_comp;

vector<vector<int>> bcc;
vector<int> tree[maxn];

vector<pii> grafo[maxn];

stack<int> stk;

void make_component(int last)
{
	bcc.push_back(vector<int>());

	while (!stk.empty())
	{
		int e = stk.top(); stk.pop();

		bcc.back().push_back(e);

		if (e == last) break;
	}
}

void lowlink(int u, bool isroot)
{
	in[u] = low[u] = ++tt;
	++sz_comp;

	bool fwd = 0;

	for (auto pp: grafo[u])
	{
		int v = pp.ff, e = pp.ss;
		if (mark_edge[e]) continue;

		mark_edge[e] = 1;
		stk.push(e);

		if (in[v])
		{
			low[u] = min(low[u], in[v]);
			continue;
		}

		lowlink(v, 0);

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

		if (isroot ? fwd : (low[v] >= in[u]))
		{
			art[u] = 1;
			make_component(e);
		}

		fwd = 1;
	}
}

int sub[maxn];
bool vis[maxn];

ll ans, dp[maxn];

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

ll choose3(int x)
{
	return 1ll*x*(x-1)*(x-2);
}

void dfs(int u, int p)
{
	vis[u] = 1;
	sub[u] = (u <= n ? 1 : sz_bcc[u]);

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

		dfs(v, u);

		if (u <= n)
		{
			dp[u] += 1ll*sub[u]*sub[v];
			dp[u] += choose2(sz_bcc[v]);
			dp[u] += 1ll*sz_bcc[v]*((ll)tree[v].size()-1);
		}

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

void solve(int u, int p)
{
	for (auto v: tree[u])
		ans -= 2ll*(u <= n ? 1 : sz_bcc[u])*dp[v];

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

		int old_sub_v = sub[v], old_sub_u = sub[u];
		ll old_dp_v = dp[v], old_dp_u = dp[u];

		if (u <= n)
		{
			int sz = sz_bcc[v];

			dp[v] += (dp[u] - dp[v] - 1ll*sub[v]*(sub[u]-sub[v]) - choose2(sz) - 1ll*sz*((ll)tree[v].size()-1));
			dp[u] -= (old_dp_v + 1ll*sub[v]*(sub[u]-sub[v]) + choose2(sz) + 1ll*sz*((ll)tree[v].size()-1));
		}
		else
		{
			int sz = sz_bcc[u];

			dp[v] += (dp[u] - dp[v] + 1ll*sub[v]*(sub[u]-sub[v]) + choose2(sz) + 1ll*sz*((ll)tree[u].size()-1));
			dp[u] -= old_dp_v;
		}

		sub[v] = sub[u];
		sub[u] -= old_sub_v;

		solve(v, u);

		sub[v] = old_sub_v, sub[u] = old_sub_u;
		dp[v] = old_dp_v, dp[u] = old_dp_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, i});
		grafo[v].push_back({u, i});

		edge[i] = {u, v};
	}

	for (int i = 1; i <= n; i++)
	{
		if (in[i]) continue;
		tt = 0;

		sz_comp = 0;

		int l = bcc.size();

		lowlink(i, 1);
		make_component(0);

		int r = bcc.size();

		ans += choose3(sz_comp);

		for (int j = l; j < r; j++)
		{
			vector<int> v;

			for (auto e: bcc[j])
			{
				v.push_back(edge[e].ff);
				v.push_back(edge[e].ss);
			}

			sort(all(v));
			v.erase(unique(all(v)), v.end());

			for (auto u: v)
			{
				if (art[u])
				{
					tree[n+j+1].push_back(u);
					tree[u].push_back(n+j+1);
				}
				else
				{
					sz_bcc[n+j+1]++;
				}
			}
		}
	}

	for (int i = 1; i <= 2*n; i++)
	{
		if (!vis[i] && tree[i].size())
		{
			dfs(i, 0);
			solve(i, 0);
		}
	}

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

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 27624 KB Output is correct
2 Correct 131 ms 28808 KB Output is correct
3 Correct 148 ms 34280 KB Output is correct
4 Correct 126 ms 29780 KB Output is correct
5 Correct 133 ms 28508 KB Output is correct
6 Correct 164 ms 33120 KB Output is correct
7 Correct 152 ms 30624 KB Output is correct
8 Correct 160 ms 31424 KB Output is correct
9 Correct 182 ms 27808 KB Output is correct
10 Correct 134 ms 27424 KB Output is correct
11 Correct 108 ms 22432 KB Output is correct
12 Correct 110 ms 22432 KB Output is correct
13 Correct 100 ms 21728 KB Output is correct
14 Correct 94 ms 21664 KB Output is correct
15 Correct 64 ms 20128 KB Output is correct
16 Correct 69 ms 20128 KB Output is correct
17 Correct 16 ms 14032 KB Output is correct
18 Correct 16 ms 13924 KB Output is correct
19 Correct 16 ms 14048 KB Output is correct
20 Correct 15 ms 13920 KB Output is correct
21 Correct 13 ms 13920 KB Output is correct
22 Correct 13 ms 13920 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9996 KB Output is correct
2 Correct 7 ms 9964 KB Output is correct
3 Correct 8 ms 9964 KB Output is correct
4 Correct 8 ms 10092 KB Output is correct
5 Correct 8 ms 10092 KB Output is correct
6 Correct 8 ms 10092 KB Output is correct
7 Correct 9 ms 10092 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 8 ms 9964 KB Output is correct
10 Correct 8 ms 9964 KB Output is correct
11 Correct 8 ms 9964 KB Output is correct
12 Correct 8 ms 9964 KB Output is correct
13 Correct 8 ms 9964 KB Output is correct
14 Correct 9 ms 9964 KB Output is correct
15 Correct 8 ms 9836 KB Output is correct
16 Correct 7 ms 9836 KB Output is correct
17 Correct 8 ms 9964 KB Output is correct
18 Correct 7 ms 9964 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 8 ms 9964 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 28444 KB Output is correct
2 Correct 148 ms 28572 KB Output is correct
3 Correct 170 ms 28572 KB Output is correct
4 Correct 155 ms 28572 KB Output is correct
5 Correct 137 ms 28444 KB Output is correct
6 Correct 188 ms 42652 KB Output is correct
7 Correct 174 ms 38044 KB Output is correct
8 Correct 163 ms 37272 KB Output is correct
9 Correct 169 ms 34332 KB Output is correct
10 Correct 169 ms 28592 KB Output is correct
11 Correct 150 ms 28456 KB Output is correct
12 Correct 151 ms 28444 KB Output is correct
13 Correct 145 ms 28444 KB Output is correct
14 Correct 140 ms 27036 KB Output is correct
15 Correct 141 ms 25500 KB Output is correct
16 Correct 75 ms 21148 KB Output is correct
17 Correct 87 ms 26004 KB Output is correct
18 Correct 84 ms 26064 KB Output is correct
19 Correct 91 ms 26184 KB Output is correct
20 Correct 93 ms 26124 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9964 KB Output is correct
3 Incorrect 8 ms 9964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 28444 KB Output is correct
2 Correct 151 ms 28628 KB Output is correct
3 Incorrect 150 ms 27104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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