Submission #103234

#	Time	Username	Problem	Language	Result	Execution time	Memory
103234		E869120	Duathlon (APIO18_duathlon)	C++14	47 / 100	158 ms	13760 KiB

count_triplets

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, M, A[200009], B[200009], col[100009], col2[100009], dp[100009], cnt1, cnt2, cnts, cntv;
vector<int>X[100009], Y[100009], V;
vector<int>G[59][59];

void dfs(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts; cnt1 += 1; cnt2 += X[pos].size();
	for (int i = 0; i < X[pos].size(); i++) {
		dfs(X[pos][i]);
	}
}

void dfs2(int pos) {
	if (col2[pos] >= 1) return;
	col2[pos] = cntv;
	for (int i = 0; i < Y[pos].size(); i++) {
		dfs2(Y[pos][i]);
	}
}

void dfs3(int pos) {
	dp[pos] = 1; V.push_back(pos);
	for (int i = 0; i < X[pos].size(); i++) {
		if (dp[X[pos][i]] >= 1) continue;
		dfs3(X[pos][i]);
		dp[pos] += dp[X[pos][i]];
	}
}

long long solve_subtask2() {
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		cnts++; dfs(i);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) Y[j].clear();
		for (int j = 1; j <= M; j++) {
			if (A[j] == i || B[j] == i) continue;
			Y[A[j]].push_back(B[j]);
			Y[B[j]].push_back(A[j]);
		}

		cntv = 0;
		for (int j = 1; j <= N; j++) col2[j] = 0;
		for (int j = 1; j <= N; j++) {
			if (col2[j] >= 1) continue;
			cntv++; dfs2(j);
		}

		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (col[j] != col[k]) continue;
				if (col2[j] != col2[k]) G[j][k].push_back(i);
			}
		}
	}

	int cnt = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (i == j || i == k || j == k || col[i] != col[j] || col[j] != col[k]) continue;

				int d[55]; for (int l = 0; l < 55; l++) d[l] = 0;
				for (int l : G[i][j]) d[l]++;
				for (int l : G[j][k]) d[l]++;

				bool flag = false;
				for (int l = 0; l < 55; l++) {
					if (d[l] >= 2 && l != j) flag = true;
				}

				if (flag == false) {
					cnt++;
				}
			}
		}
	}
	return 1LL * cnt;
}

long long solve_subtask3() {
	long long ans = 0; cnts = 1;
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		cnt1 = 0; cnt2 = 0;
		dfs(i); cnt2 /= 2;

		if (cnt1 == cnt2) ans += 1LL * cnt1 * (cnt1 - 1) * (cnt1 - 2);
		else ans += 1LL * cnt1 * (cnt1 - 1) * (cnt1 - 2) / 3LL;
	}
	return ans;
}

long long solve_subtask5() {
	long long ans = 0;
	for (int i = 1; i <= N; i++) {
		if (dp[i] >= 1) continue;
		V.clear();
		dfs3(i);

		long long size_ = V.size();
		ans += size_ * (size_ - 1) * (size_ - 2);

		for (int pos : V) {
			long long rem = size_ - 1;
			for (int j = 0; j < X[pos].size(); j++) {
				if (dp[X[pos][j]] > dp[pos]) continue;
				ans -= dp[X[pos][j]] * (dp[X[pos][j]] - 1);
				rem -= dp[X[pos][j]];
			}
			ans -= rem * (rem - 1);
		}
	}
	return ans;
}

int main() {
	scanf("%lld%lld", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%lld%lld", &A[i], &B[i]);
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	
	int max_degree = 0;
	for (int i = 1; i <= N; i++) max_degree = max(max_degree, (int)X[i].size());

	if (N <= 50 && M <= 100) {
		cout << solve_subtask2() << endl;
	}
	else if (max_degree <= 2) {
		cout << solve_subtask3() << endl;
	}
	else {
		cout << solve_subtask5() << endl;
	}
	return 0;
}

Compilation message (stderr)

count_triplets.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int)':
count_triplets.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs3(int)':
count_triplets.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int solve_subtask5()':
count_triplets.cpp:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < X[pos].size(); j++) {
                    ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 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