Submission #242690

#	Time	Username	Problem	Language	Result	Execution time	Memory
242690		iefnah06	Duathlon (APIO18_duathlon)	C++98	100 / 100	202 ms	27512 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m;
vector<vector<int> > edges;

vector<int> sidx;
int curidx;
vector<int> sbcc;
vector<vector<int> > bedges;
vector<int> stk;

int dfs(int v, int& nv) {
	sidx[v] = curidx;
	int lowval = curidx;
	curidx++;
	stk.push_back(v);
	nv++;
	for (size_t j = 0; j < edges[v].size(); j++) {
		int w = edges[v][j];
		if (sidx[w] == -1) {
			int wlowval = dfs(w, nv);
			if (wlowval == sidx[v]) {
				bedges.push_back(vector<int>());
				sbcc.push_back(0);
				while (true) {
					int t = stk.back();
					stk.pop_back();
					bedges.back().push_back(t);
					bedges[t].push_back(int(bedges.size())-1);
					sbcc.back() += 1;
					if (t == w) break;
				}
				bedges.back().push_back(v);
				bedges[v].push_back(int(bedges.size())-1);
				sbcc.back() += 1;
			} else {
				lowval = min(lowval, wlowval);
			}
		} else {
			lowval = min(lowval, sidx[w]);
		}
	}
	return lowval;
}

ll total = 0;

int dfs2(int v, int p, int nv) {
	int sz = (v < n);
	int cur = v < n ? -1 : sbcc[v-n];
	for (size_t j = 0; j < bedges[v].size(); j++) {
		int w = bedges[v][j];
		if (w == p) continue;
		int wsz = dfs2(w, v, nv);
		total += ll(wsz) * sz * cur;
		sz += wsz;
	}
	total += ll(nv - sz) * sz * cur;
	return sz;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	edges.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	sidx.assign(n, -1);
	bedges.reserve(2*n);
	stk.reserve(n);
	sbcc.reserve(n);
	bedges.resize(n);
	for (int i = 0; i < n; i++) {
		if (sidx[i] == -1) {
			int nv = 0;
			stk.clear();
			dfs(i, nv);
			int sz = dfs2(i, -1, nv);
			assert(sz == nv);
		}
	}
	total *= 2;
	cout << total << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10