제출 #364881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364881		Drew_	Duathlon (APIO18_duathlon)	C++14	23 / 100	166 ms	24940 KiB

count_triplets

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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