oj.uz

Submission #364879

# Submission time Handle Problem Language Result Execution time Memory
364879 2021-02-10T10:47:55 Z Drew_ Duathlon (APIO18_duathlon) C++14
31 / 100
 141 ms 20420 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

int const MAX = 1e5 + 7;

ii ds[MAX]; // [node]: {parent, size}
int frep(int x)
{
	return ds[x].f1 == x ? x : ds[x].f1 = frep(ds[x].f1);
}

void join(int a, int b)
{
	a = frep(a); b = frep(b);
	if (a == b)
		return;

	ds[a].f1 = b;
	ds[b].s2 += ds[a].s2;
}

vector<ii> adj[MAX]; //[from]: {to, index}
vector<ii> edge; //[index]: {from, to}
bool bridge[2 * MAX];

int disc[MAX];
int low[MAX];
static int ctr = 0;
void getBridge(int node, int par)
{
	disc[node] = low[node] = ctr++;
	for (ii to : adj[node]) 
	{
		if (disc[to.f1] == -1)
		{
			getBridge(to.f1, node);
			if (low[to.f1] > disc[node])
				bridge[to.s2] = true;

			low[node] = min(low[node], low[to.f1]);
		}
		else if (to.f1 != par)
			low[node] = min(low[node], disc[to.f1]);
	}
}

bool vst[MAX];

vector<int> tree[MAX];
static ll res = 0;

int child[MAX];
vector<int> euler;
void dfs(int node)
{
	euler.pb(node);
	vst[node] = true;
	child[node] = ds[node].s2;

	for (int to : tree[node])
	{
		if (!vst[to])
		{
			dfs(to);
			child[node] += child[to];
		}
	}
}

void solve(int root)
{
	euler.clear();
	dfs(root);

	int all = 0;
	for (int node : euler)
		all += ds[node].s2;

	for (int node : euler)
	{
		//s, c, f from the same cycle
		res += 1LL * ds[node].s2 * (ds[node].s2 - 1) * (ds[node].s2 - 2);


		//s from other; c,f from the same
		//f from other; s,c from the same
		for (int to : tree[node])
		{
			int sz = child[to];
			if (child[node] < child[to]) //to is the parent
				sz = child[root] - child[node];

			res += 2LL * sz * (ds[node].s2 - 1) * (ds[node].s2 - 1);
		}

		all -= ds[node].s2; //exclude itself

		//s and f from other; c from the same
		for (int to : tree[node])
		{
			int sz = child[to];
			if (child[node] < child[to]) sz = child[root] - child[node];

			res += 1LL * sz * ds[node].s2 * (all - sz);
		}

		all += ds[node].s2; //include back
	}
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < MAX; ++i)
	{
		ds[i] = {i, 1};
		disc[i] = -1;
	}

	int n, m;
	cin >> n >> m;

	edge.resize(m);
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;

		edge[i] = {u, v};
		adj[u].pb({v, i});
		adj[v].pb({u, i});
	}

	for (int i = 1; i <= n; ++i)
		if (disc[i] == -1)
			getBridge(i, -1);

	for (int i = 0; i < m; ++i)
	{
		if (!bridge[i])
			join(edge[i].f1, edge[i].s2);
	}

	for (int i = 0; i < m; ++i)
	{
		if (bridge[i])
		{
			int u = frep(edge[i].f1);
			int v = frep(edge[i].s2);

			tree[u].pb(v);
			tree[v].pb(u);
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!vst[frep(i)])
		{
			solve(frep(i));
		}
	}

	cout << res << '\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6272 KB Output is correct
4 Correct 5 ms 6252 KB Output is correct
5 Correct 5 ms 6252 KB Output is correct
6 Correct 4 ms 6252 KB Output is correct
7 Incorrect 4 ms 6252 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 81 ms 19672 KB Output is correct
2 Correct 76 ms 19564 KB Output is correct
3 Correct 96 ms 18312 KB Output is correct
4 Correct 82 ms 19180 KB Output is correct
5 Correct 84 ms 16492 KB Output is correct
6 Correct 100 ms 17132 KB Output is correct
7 Correct 97 ms 15980 KB Output is correct
8 Correct 94 ms 16876 KB Output is correct
9 Correct 98 ms 15104 KB Output is correct
10 Correct 93 ms 15616 KB Output is correct
11 Correct 75 ms 13804 KB Output is correct
12 Correct 78 ms 13548 KB Output is correct
13 Correct 66 ms 13548 KB Output is correct
14 Correct 63 ms 13292 KB Output is correct
15 Correct 61 ms 12652 KB Output is correct
16 Correct 63 ms 12524 KB Output is correct
17 Correct 7 ms 7148 KB Output is correct
18 Correct 7 ms 7148 KB Output is correct
19 Correct 7 ms 7148 KB Output is correct
20 Correct 7 ms 7148 KB Output is correct
21 Correct 8 ms 7040 KB Output is correct
22 Correct 7 ms 7148 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16876 KB Output is correct
2 Correct 131 ms 16876 KB Output is correct
3 Correct 115 ms 17004 KB Output is correct
4 Correct 106 ms 16880 KB Output is correct
5 Correct 118 ms 16876 KB Output is correct
6 Correct 130 ms 20420 KB Output is correct
7 Correct 141 ms 19432 KB Output is correct
8 Correct 123 ms 18932 KB Output is correct
9 Correct 118 ms 18024 KB Output is correct
10 Correct 114 ms 16748 KB Output is correct
11 Correct 117 ms 16880 KB Output is correct
12 Correct 101 ms 16492 KB Output is correct
13 Correct 119 ms 16492 KB Output is correct
14 Correct 94 ms 15724 KB Output is correct
15 Correct 90 ms 15084 KB Output is correct
16 Correct 52 ms 12908 KB Output is correct
17 Correct 64 ms 17632 KB Output is correct
18 Correct 68 ms 17500 KB Output is correct
19 Correct 70 ms 17620 KB Output is correct
20 Correct 69 ms 17500 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16876 KB Output is correct
2 Correct 114 ms 16744 KB Output is correct
3 Incorrect 115 ms 16236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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