Submission #358217

#	Time	Username	Problem	Language	Result	Execution time	Memory
358217		shivensinha4	Duathlon (APIO18_duathlon)	C++17	0 / 100	1141 ms	733932 KiB

count_triplets

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e5;
vi adj[MXN], apAdj[MXN];
int low[MXN], tin[MXN], sz[MXN], initSz[MXN], apComp[MXN];
bool ap[MXN], vis[MXN], seen[MXN];
vector<vi> comp;
int pt = 0, m;
ll rem = 0, n;

void dfs(int p, int parent) {
	comp[comp.size()-1].push_back(p);
	vis[p] = true;
	low[p] = tin[p] = pt++;
	bool seenChild = false;
	for (auto &i: adj[p]) if (i != parent) {
		if (vis[i]) {
			low[p] = min(low[p], tin[i]);
			continue;
		}
		
		dfs(i, p);
		
		if (seenChild and parent == p) ap[p] = true;
		else seenChild = true;
		
		low[p] = min(low[p], low[i]);
		if (low[i] >= tin[p] and parent != p) ap[p] = true;
		
		low[p] = min(low[p], low[i]);
	}
}

void findSz(int p, int parent) {
	sz[p] = initSz[p];
	for (auto &i: apAdj[p]) if (i != parent) {
		findSz(i, p);
		sz[p] += sz[i];
	}
}

void reroot(int p, int parent) {
	for (auto &i: apAdj[p]) {
		rem += sz[i] * (sz[i]-1) + (initSz[p]-1) * sz[i] * (sz[i]+1);
		if (i != parent) {
			sz[p] -= sz[i];
			sz[i] += sz[p];
			reroot(i, p);
			sz[i] -= sz[p];
			sz[p] += sz[i];
		}
	}
}


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for_(i, 0, m) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	
	for_(i, 0, n) if (!vis[i]) {
		comp.push_back({});
		dfs(i, i);
	}
	
	for_(i, 0, n) if (adj[i].size() == 1) ap[i] = true;
	
	for (auto &c: comp) {
		vi apList;
		for (int &i: c) if (ap[i]) apList.push_back(i);
		queue<int> q;
		q.push(apList[0]);
		seen[apList[0]] = true;
		while (q.size()) {
			int p = q.front(); q.pop();
			apComp[p] = p;
			initSz[p]++;
			for (auto &i: adj[p]) {
				if (ap[i]) {
					apAdj[p].push_back(i);
					if (!seen[i]) {
						seen[i] = true;
						q.push(i);
					}
				}
				else {
					initSz[p]++;
					apComp[i] = p;
				}
			}
		}
		
		findSz(apList[0], apList[0]);
		reroot(apList[0], apList[0]);
	}
	
	cout << n*(n-1)*(n-2) - rem << endl;
	
	
	return 0;
}

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