Submission #364955

#	Time	Username	Problem	Language	Result	Execution time	Memory
364955		Drew_	Duathlon (APIO18_duathlon)	C++14	31 / 100	207 ms	25832 KiB

count_triplets

#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
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10