oj.uz

Submission #364887

# Submission time Handle Problem Language Result Execution time Memory
364887 2021-02-10T11:24:02 Z Drew_ Duathlon (APIO18_duathlon) C++14
31 / 100
 168 ms 19560 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//#define int long long

#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 arti[MAX];

int disc[MAX];
int low[MAX];
int child_ctr[MAX];
static int ctr = 0;
void getArti(int node, int par)
{
	disc[node] = low[node] = ctr++;
	for (ii to : adj[node]) 
	{
		if (disc[to.f1] == -1)
		{
			child_ctr[node]++;	
			getArti(to.f1, node);
			if (low[to.f1] >= disc[node])
				arti[node] = 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)
	{
		//cerr << node << ": " << ds[node].s2 << '\n';
		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
	}
}

int32_t 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)
		{
			getArti(i, -1);
			arti[i] = (child_ctr[i] >= 2);	
		}
	}

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

		if (!arti[u] && !arti[v])
			join(u, v);
	}

	for (int i = 0; i < m; ++i)
	{
		if (arti[edge[i].f1] || arti[edge[i].s2])
		{
			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 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6252 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 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 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6252 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 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 86 ms 18796 KB Output is correct
2 Correct 82 ms 18796 KB Output is correct
3 Correct 117 ms 17388 KB Output is correct
4 Correct 100 ms 18412 KB Output is correct
5 Correct 115 ms 15492 KB Output is correct
6 Correct 125 ms 16236 KB Output is correct
7 Correct 128 ms 15248 KB Output is correct
8 Correct 128 ms 15980 KB Output is correct
9 Correct 118 ms 14316 KB Output is correct
10 Correct 110 ms 14700 KB Output is correct
11 Correct 118 ms 12780 KB Output is correct
12 Correct 87 ms 12652 KB Output is correct
13 Correct 81 ms 12396 KB Output is correct
14 Correct 76 ms 12268 KB Output is correct
15 Correct 56 ms 11372 KB Output is correct
16 Correct 53 ms 11244 KB Output is correct
17 Correct 8 ms 7532 KB Output is correct
18 Correct 8 ms 7532 KB Output is correct
19 Correct 9 ms 7404 KB Output is correct
20 Correct 8 ms 7404 KB Output is correct
21 Correct 8 ms 7404 KB Output is correct
22 Correct 7 ms 7404 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 5 ms 6380 KB Output is correct
3 Correct 6 ms 6384 KB Output is correct
4 Correct 5 ms 6380 KB Output is correct
5 Correct 5 ms 6380 KB Output is correct
6 Correct 5 ms 6380 KB Output is correct
7 Correct 5 ms 6380 KB Output is correct
8 Correct 6 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 6 ms 6380 KB Output is correct
13 Correct 5 ms 6380 KB Output is correct
14 Correct 5 ms 6252 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 135 ms 16004 KB Output is correct
2 Correct 125 ms 15980 KB Output is correct
3 Correct 120 ms 15964 KB Output is correct
4 Correct 140 ms 15984 KB Output is correct
5 Correct 140 ms 15908 KB Output is correct
6 Correct 168 ms 19560 KB Output is correct
7 Correct 138 ms 18536 KB Output is correct
8 Correct 152 ms 17768 KB Output is correct
9 Correct 132 ms 17128 KB Output is correct
10 Correct 131 ms 15724 KB Output is correct
11 Correct 130 ms 15984 KB Output is correct
12 Correct 127 ms 15552 KB Output is correct
13 Correct 127 ms 15612 KB Output is correct
14 Correct 108 ms 14956 KB Output is correct
15 Correct 98 ms 14244 KB Output is correct
16 Correct 53 ms 11884 KB Output is correct
17 Correct 76 ms 16224 KB Output is correct
18 Correct 77 ms 16220 KB Output is correct
19 Correct 68 ms 16340 KB Output is correct
20 Correct 75 ms 16220 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 132 ms 15980 KB Output is correct
2 Correct 126 ms 15848 KB Output is correct
3 Incorrect 163 ms 15848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6252 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 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 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6252 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 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 -