oj.uz

Submission #364881

# Submission time Handle Problem Language Result Execution time Memory
364881 2021-02-10T11:14:13 Z Drew_ Duathlon (APIO18_duathlon) C++14
23 / 100
 166 ms 24940 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);
			if (child[i] >= 2)
				arti[i] = true;
		}
	}

	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 Incorrect 6 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 21608 KB Output is correct
2 Correct 154 ms 21480 KB Output is correct
3 Correct 129 ms 21480 KB Output is correct
4 Correct 135 ms 21480 KB Output is correct
5 Correct 137 ms 21596 KB Output is correct
6 Correct 154 ms 24940 KB Output is correct
7 Correct 166 ms 24424 KB Output is correct
8 Correct 142 ms 23632 KB Output is correct
9 Correct 141 ms 22760 KB Output is correct
10 Correct 126 ms 20972 KB Output is correct
11 Correct 133 ms 21608 KB Output is correct
12 Correct 126 ms 20716 KB Output is correct
13 Correct 157 ms 20976 KB Output is correct
14 Correct 120 ms 19564 KB Output is correct
15 Correct 101 ms 18796 KB Output is correct
16 Correct 59 ms 15980 KB Output is correct
17 Correct 76 ms 21084 KB Output is correct
18 Correct 84 ms 20820 KB Output is correct
19 Correct 84 ms 21320 KB Output is correct
20 Correct 78 ms 20456 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 21480 KB Output is correct
2 Correct 152 ms 21352 KB Output is correct
3 Incorrect 153 ms 22764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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