oj.uz

Submission #371451

# Submission time Handle Problem Language Result Execution time Memory
371451 2021-02-26T16:05:05 Z luciocf Duathlon (APIO18_duathlon) C++14
31 / 100
 192 ms 40860 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[u] -= (dp[v] + 1ll*sub[v]*(sub[u]-sub[v]) + choose2(sz) + 1ll*sz*((ll)tree[v].size()-1));
			dp[v] += dp[u];
		}
		else
		{
			int sz = sz_bcc[u];

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

		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 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Incorrect 6 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 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Incorrect 6 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 101 ms 27624 KB Output is correct
2 Correct 98 ms 27624 KB Output is correct
3 Correct 153 ms 31704 KB Output is correct
4 Correct 110 ms 28500 KB Output is correct
5 Correct 130 ms 26332 KB Output is correct
6 Correct 141 ms 30944 KB Output is correct
7 Correct 160 ms 28764 KB Output is correct
8 Correct 143 ms 29376 KB Output is correct
9 Correct 137 ms 26144 KB Output is correct
10 Correct 146 ms 25860 KB Output is correct
11 Correct 96 ms 21280 KB Output is correct
12 Correct 109 ms 21536 KB Output is correct
13 Correct 84 ms 20640 KB Output is correct
14 Correct 87 ms 20776 KB Output is correct
15 Correct 66 ms 19360 KB Output is correct
16 Correct 64 ms 19360 KB Output is correct
17 Correct 13 ms 13924 KB Output is correct
18 Correct 13 ms 13924 KB Output is correct
19 Correct 13 ms 13920 KB Output is correct
20 Correct 13 ms 13920 KB Output is correct
21 Correct 15 ms 14048 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 9964 KB Output is correct
2 Correct 7 ms 9964 KB Output is correct
3 Correct 7 ms 9964 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10092 KB Output is correct
6 Correct 8 ms 10092 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 7 ms 9964 KB Output is correct
9 Correct 7 ms 9964 KB Output is correct
10 Correct 7 ms 9964 KB Output is correct
11 Correct 7 ms 9964 KB Output is correct
12 Correct 7 ms 9964 KB Output is correct
13 Correct 7 ms 9964 KB Output is correct
14 Correct 7 ms 9964 KB Output is correct
15 Correct 7 ms 9964 KB Output is correct
16 Correct 7 ms 9836 KB Output is correct
17 Correct 7 ms 9964 KB Output is correct
18 Correct 7 ms 9964 KB Output is correct
19 Correct 7 ms 9964 KB Output is correct
20 Correct 7 ms 9964 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 28572 KB Output is correct
2 Correct 154 ms 28444 KB Output is correct
3 Correct 136 ms 28492 KB Output is correct
4 Correct 153 ms 28608 KB Output is correct
5 Correct 131 ms 28444 KB Output is correct
6 Correct 192 ms 40860 KB Output is correct
7 Correct 186 ms 36892 KB Output is correct
8 Correct 159 ms 36248 KB Output is correct
9 Correct 150 ms 33692 KB Output is correct
10 Correct 139 ms 28444 KB Output is correct
11 Correct 144 ms 28512 KB Output is correct
12 Correct 137 ms 28444 KB Output is correct
13 Correct 156 ms 28484 KB Output is correct
14 Correct 132 ms 27036 KB Output is correct
15 Correct 115 ms 25500 KB Output is correct
16 Correct 68 ms 21148 KB Output is correct
17 Correct 91 ms 26072 KB Output is correct
18 Correct 83 ms 26064 KB Output is correct
19 Correct 87 ms 26316 KB Output is correct
20 Correct 86 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 8 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 151 ms 28560 KB Output is correct
2 Correct 138 ms 28700 KB Output is correct
3 Incorrect 149 ms 27252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Incorrect 6 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 6 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Incorrect 6 ms 9708 KB Output isn't correct
8 Halted 0 ms 0 KB -