Submission #63563

#	Time	Username	Problem	Language	Result	Execution time	Memory
63563		kingpig9	Duathlon (APIO18_duathlon)	C++11	100 / 100	463 ms	142548 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5 + 10;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void setmin (int &a, int b) {
	if (a > b) {
		a = b;
	}
}

int N, M;
vector<int> adj[MAXN];
int par[MAXN], num[MAXN], low[MAXN];
vector<pii> stk;
vector<vector<pii>> vbcc;

void dfs (int x, bool isroot = false) {
	static int cur = 0;
	num[x] = low[x] = cur++;

	int nchild = 0;
	for (int y : adj[x]) {
		if (y != par[x]) {
			if (num[y] == -1) {
				nchild++;
				par[y] = x;
				stk.push_back({x, y});
				dfs(y);
				setmin(low[x], low[y]);

				if (isroot ? (nchild > 1) : (num[x] <= low[y])) {
					//then it is bcc
					debug("IS BCC:");
					vector<pii> v;
					pii bck;
					do {
						bck = stk.back();
						stk.pop_back();
						v.push_back(bck);
						debug(" (%d, %d)", bck.fi, bck.se);
					} while (bck != pii(x, y));
					debug("\n");
					vbcc.push_back(v);
				}
			} else if (num[x] > num[y]) {
				//if you go to higher edge
				setmin(low[x], num[y]);
				stk.push_back({x, y});
			}
		}
	}
}

int C;	//B = # of BCCs
int szcmp[MAXN];
vector<int> cadj[MAXN];

void find_bcc() {
	for (int i = 0; i < N; i++) {
		num[i] = -1;
	}

	for (int i = 0; i < N; i++) {
		if (num[i] == -1) {
			dfs(i, true);
			if (!stk.empty()) {
				vbcc.push_back(stk);
				stk.clear();
			}
		}
	}

	for (vector<pii> v : vbcc) {
		set<int> verts;
		debug("BCC:");
		for (pii p : v) {
			verts.insert(p.fi);
			verts.insert(p.se);
			debug(" (%d, %d)", p.fi, p.se);
		}
		debug("\n");
		int y = N + C;
		szcmp[y] = verts.size();
		for (int x : verts) {
			cadj[x].push_back(y);
			cadj[y].push_back(x);
			debug("cadj %d %d\n", x, y);
		}
		C++;
	}
}

ll ans;

int croot, csize;
int sub[MAXN];
bool vis[MAXN];

void dfs1 (int x, int p) {
	vis[x] = true;
	sub[x] = (x < N);
	for (int y : cadj[x]) {
		if (y != p) {
			dfs1(y, x);
			sub[x] += sub[y];
		}
	}
}

void dfs2 (int x, int p) {
	if (x < N) {
		for (int y : cadj[x]) {
			int s = (y == p ? sub[x] : csize - sub[y]);
			ans -= ll(szcmp[y] - 1) * s * (s - 1);
			debug("ans -= %d * %d * %d\n", szcmp[y] - 1, s, s - 1);
		}
	}

	for (int y : cadj[x]) {
		if (y != p) {
			dfs2(y, x);
		}
	}
}

void compute() {
	for (croot = 0; croot < N; croot++) {
		if (vis[croot]) {
			continue;
		}
		dfs1(croot, -1);
		csize = sub[croot];
		ans += csize * ll(csize - 1) * (csize - 2);
		debug("ans += %d * %d * %d\n", csize, csize - 1, csize - 2);
		dfs2(croot, -1);
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	find_bcc();
	compute();

	printf("%lld\n", ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

• 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