Submission #565282

#	Time	Username	Problem	Language	Result	Execution time	Memory
565282		Drew_	Duathlon (APIO18_duathlon)	C++17	31 / 100	129 ms	32012 KiB

count_triplets

#include <bits/stdc++.h>
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

const int MAX = 1e5 + 7;

static ll ans = 0;

int N, M;
bitset<MAX> arti;
vector<ii> edge; //[index]: {from, to}
vector<int> adj[MAX]; //[from]: to

// bct
int compsz;
int id[MAX], sz[2*MAX];
vector<int> tree[2*MAX];

// solve
bitset<2 * MAX> vst;
int child_sz[2 * MAX], parent[2 * MAX];
vector<int> nodes;

void build_bct()
{
	int disc[MAX], low[MAX];
	vector<vector<int>> comps;

	int ctr = 1;
	vector<int> sk;
	const auto getArti = [&](const auto &self, int node, int par) -> void
	{
		disc[node] = low[node] = ctr++;
		sk.pb(node);

		for (int to : adj[node]) if (to != par)
		{
			if (disc[to] == -1)
			{
				self(self, to, node);
				low[node] = min(low[node], low[to]);

				if (low[to] >= disc[node])
				{	
					arti[node] = (par != -1 || disc[to] > 1 + disc[node]);
					
					comps.pb({node});
					for (; comps.back().back() != to; sk.pop_back())
						comps.back().pb(sk.back());
				}
			}
			else low[node] = min(low[node], disc[to]);
		}
	};

	memset(disc, -1, sizeof(disc));
	memset(low, -1, sizeof(low));
	comps.clear();
	ctr = 1;

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

	// build tree
	ctr = 1;
	for (int i = 1; i <= N; ++i) if (arti[i])
		sz[ctr] = 1, id[i] = ctr++;

	for (auto &comp : comps)
	{
		sz[ctr] = (int)comp.size();
		for (int node : comp)
		{
			if (!arti[node]) id[node] = ctr;
			else
			{
				sz[ctr]--;
				tree[ctr].pb(id[node]);
				tree[id[node]].pb(ctr);

				// cerr << ctr << " - " << id[node] << '\n';
			}
		}
		ctr++;
	}
	compsz = ctr - 1;

	// s and f from other two same group; c from the same
	ctr = 1;
	for (int i = 1; i <= N; ++i) if (arti[i])
	{
		for (int to : tree[ctr])
			ans += 1ll * sz[to] * (sz[to] - 1);
		ctr++;
	}
}

int dfs(int node)
{
	vst[node] = true;
	child_sz[node] = sz[node];
	nodes.pb(node);
	for (int to : tree[node]) if (to != parent[node])
			parent[to] = node, child_sz[node] += dfs(to);
	return child_sz[node];
}



void solve(int root)
{
	nodes.clear();
	
	parent[root] = -1;
	int all = dfs(root);
	for (int node : nodes)
	{
		//s, c, f from the same cycle
		ans += 1LL * sz[node] * (sz[node] - 1) * (sz[node] - 2);

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

			ans += 2ll * tmp * sz[node] * (sz[node] - 1);
		}

		//s and f from other two different group; c from the same
		for (int to : tree[node])
		{
			int tmp = child_sz[to];
			if (parent[node] == to)
				tmp = child_sz[root] - child_sz[node];

			// cerr << to << " " << tmp << '\n';

			ans += 1ll * tmp * sz[node] * (all - tmp - sz[node]);			
		}
	} 
}

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

	cin >> N >> M;

	edge.resize(M);
	for (auto &[u, v] : edge)
	{
		cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}

	build_bct();
	
	for (int i = 1; i <= compsz; ++i) if (!vst[i])
		solve(i);

	cout << ans << '\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