oj.uz

Submission #364955

# Submission time Handle Problem Language Result Execution time Memory
364955 2021-02-10T15:26:37 Z Drew_ Duathlon (APIO18_duathlon) C++14
31 / 100
 207 ms 25832 KB 
#include <iostream>
#include <vector>
#include <map>
#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<int> adj[MAX]; //[from]: to
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 (int to : adj[node]) 
	{
		if (disc[to] == -1)
		{
			child_ctr[node]++;	
			getArti(to, node);
			if (low[to] >= disc[node])
				arti[node] = true;

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

bool vst[MAX];

vector<ii> 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 (ii	to : tree[node])
	{
		if (!vst[to.f1])
		{
			dfs(to.f1);
			child[node] += child[to.f1];
		}
	}
}

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)
	{
		//cerr << "[" << node << "]:\n";

		//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 (ii to : tree[node])
		{
			int sz = child[to.f1];
			if (child[node] < child[to.f1]) //to is the parent
				sz = child[root] - child[node];

			if (to.s2) res += 2LL * sz * (ds[node].s2) * (ds[node].s2 - 1);
			else res += 2LL * sz * (ds[node].s2 - 1) * (ds[node].s2 - 1);
			//cerr << sz << '\n';;
			//cerr << ds[node].s2 << " " << ds[node].s2 - 1 << " " << '\n';

			//	cerr << res << '\n';
		}


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

			res += 1LL * ds[node].s2 * sz * (ds[to.f1].s2 - 1);
			
			//cerr << "HAHA " << 1LL * ds[node].s2 * (sz) * (ds[to.f1].s2 - 1) << '\n';
		}


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

		//s and f from other two different group; c from the same
		for (ii to : tree[node])
		{
			int sz = child[to.f1];
			if (child[node] < child[to.f1]) 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);
		adj[v].pb(u);
	}

	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);
	}

	map<ii, int> tree_edge;
	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_edge[{min(u, v), max(u, v)}]++;
		}
	}

	for (auto x : tree_edge)
	{
		int u = x.f1.f1;
		int v = x.f1.s2;
		int f = x.s2;
		tree[u].pb({v, f >= 2});
		tree[v].pb({u, f >= 2});
	}

	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 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 4 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 87 ms 18796 KB Output is correct
2 Correct 85 ms 18796 KB Output is correct
3 Correct 117 ms 20588 KB Output is correct
4 Correct 101 ms 19948 KB Output is correct
5 Correct 98 ms 17644 KB Output is correct
6 Correct 123 ms 19696 KB Output is correct
7 Correct 140 ms 18924 KB Output is correct
8 Correct 122 ms 19692 KB Output is correct
9 Correct 122 ms 18028 KB Output is correct
10 Correct 113 ms 17900 KB Output is correct
11 Correct 98 ms 14956 KB Output is correct
12 Correct 86 ms 14828 KB Output is correct
13 Correct 74 ms 14188 KB Output is correct
14 Correct 74 ms 14060 KB Output is correct
15 Correct 50 ms 12268 KB Output is correct
16 Correct 54 ms 12268 KB Output is correct
17 Correct 7 ms 7532 KB Output is correct
18 Correct 7 ms 7532 KB Output is correct
19 Correct 7 ms 7404 KB Output is correct
20 Correct 7 ms 7404 KB Output is correct
21 Correct 7 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 5 ms 6508 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 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 6380 KB Output is correct
16 Correct 4 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 189 ms 22256 KB Output is correct
2 Correct 159 ms 22384 KB Output is correct
3 Correct 185 ms 22256 KB Output is correct
4 Correct 163 ms 22380 KB Output is correct
5 Correct 157 ms 22256 KB Output is correct
6 Correct 207 ms 25832 KB Output is correct
7 Correct 175 ms 24812 KB Output is correct
8 Correct 167 ms 24044 KB Output is correct
9 Correct 167 ms 23408 KB Output is correct
10 Correct 161 ms 22000 KB Output is correct
11 Correct 160 ms 22252 KB Output is correct
12 Correct 158 ms 21868 KB Output is correct
13 Correct 164 ms 21868 KB Output is correct
14 Correct 142 ms 20460 KB Output is correct
15 Correct 118 ms 19180 KB Output is correct
16 Correct 61 ms 14316 KB Output is correct
17 Correct 129 ms 22496 KB Output is correct
18 Correct 111 ms 22236 KB Output is correct
19 Correct 112 ms 22620 KB Output is correct
20 Correct 129 ms 22376 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 167 ms 22256 KB Output is correct
2 Correct 189 ms 22124 KB Output is correct
3 Incorrect 181 ms 21736 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 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 4 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 -