Submission #103247

#	Time	Username	Problem	Language	Result	Execution time	Memory
103247		E869120	Duathlon (APIO18_duathlon)	C++14	47 / 100	636 ms	40852 KiB

count_triplets

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

class UnionFind {
public:
	vector<int>par;

	void init(int sz) {
		par.resize(sz, -1);
	}
	
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}

	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u != v) par[u] = v;
	}

	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

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

map<pair<int, int>, int>Map;

void dfs(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts; V.push_back(pos); 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, int target) {
	if (pos == target) {
		for (int i = 0; i < V.size() - 1; i++) {
			cycles[Map[make_pair(V[i], V[i + 1])]] = true;
		}
		return;
	}
	used[pos] = true;
	for (int i = 0; i < Z[pos].size(); i++) {
		if (used[Z[pos][i]] == true) continue;
		V.push_back(Z[pos][i]);
		dfs3(Z[pos][i], target);
		V.pop_back();
	}
}

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

long long solve_subtask7() {
	UnionFind UF; UF.init(N + 2);
	for (int i = 1; i <= M; i++) {
		if (UF.same(A[i], B[i]) == true) {
			// この辺がサイクルに含まれる場合
			V.push_back(A[i]);
			dfs3(A[i], B[i]);
			V.clear();
			cycles[i] = true;
		}
		else {
			// この辺がサイクルに含まれない場合
			Z[A[i]].push_back(B[i]);
			Z[B[i]].push_back(A[i]);
			UF.unite(A[i], B[i]);
		}
	}

	for (int i = 1; i <= M; i++) {
		if (cycles[i] == true) continue;
		Y[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
	}

	long long FinalAns = 0;

	for (int i = 1; i <= N; i++) {
		if (col[i] >= 1) continue;
		V.clear();
		cnts++; dfs(i);

		vector<long long> dp1, dp2, dp3, dp4;
		for (int j = 0; j < V.size(); j++) {
			if (dp[V[j]] >= 1) continue;
			V2.clear(); dfs4(V[j]);

			long long A1 = 0, A2 = 0, A3 = 0;

			// dp1 の値を求める
			A1 = V2.size() - 1;

			// dp2 の値を求める
			for (int pos : V2) {
				if (pos != V[j]) A2 += (dp[pos] - 1LL);
			}

			// dp3 の値を求める
			A3 += 1LL * (long long)(V2.size() - 1) * ((long long)V2.size() - 2) * ((long long)V2.size() - 3);
			for (int pos : V2) {
				if (pos == V[j]) continue;
				long long rem = V2.size() - 2;
				for (int k = 0; k < Y[pos].size(); k++) {
					if (dp[Y[pos][k]] > dp[pos]) continue;
					A3 -= dp[Y[pos][k]] * (dp[Y[pos][k]] - 1);
					rem -= dp[Y[pos][k]];
				}
				A3 -= rem * (rem - 1);
			}

			dp1.push_back(A1);
			dp2.push_back(A2);
			dp3.push_back(A3);

			for (int k = 0; k < Y[V[j]].size(); k++) {
				dp4.push_back(dp[Y[V[j]][k]]);
			}
		}

		// 総計算
		FinalAns += 1LL * (long long)dp1.size() * ((long long)dp1.size() - 1) * ((long long)dp1.size() - 2);
		for (int j = 0; j < dp3.size(); j++) FinalAns += dp3[j];
		for (int j = 0; j < dp1.size(); j++) FinalAns += 2LL * (long long)(dp1.size() - 1) * ((long long)dp1.size() - 1) * dp1[j];
		for (int j = 0; j < dp2.size(); j++) FinalAns += 2LL * (long long)(dp1.size()) * dp2[j];
		
		long long X = 0; for (int j = 0; j < dp4.size(); j++) X += dp4[j];
		X *= X;
		for (int j = 0; j < dp4.size(); j++) X -= dp4[j] * dp4[j];
		FinalAns += X;
	}
	return FinalAns;
}

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;
}

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]); Map[make_pair(A[i], B[i])] = i;
		X[B[i]].push_back(A[i]); Map[make_pair(B[i], A[i])] = i;
	}

	if (N <= 50 && M <= 100) {
		cout << solve_subtask2() << endl;
	}
	else {
		cout << solve_subtask7() << endl;
	}
	return 0;
}

Compilation message (stderr)

count_triplets.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:43: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:51: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, int)':
count_triplets.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < V.size() - 1; i++) {
                   ~~^~~~~~~~~~~~~~
count_triplets.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs4(int)':
count_triplets.cpp:74: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 'long long int solve_subtask7()':
count_triplets.cpp:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < V.size(); j++) {
                   ~~^~~~~~~~~~
count_triplets.cpp:132:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < Y[pos].size(); k++) {
                     ~~^~~~~~~~~~~~~~~
count_triplets.cpp:144:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < Y[V[j]].size(); k++) {
                    ~~^~~~~~~~~~~~~~~~
count_triplets.cpp:151:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < dp3.size(); j++) FinalAns += dp3[j];
                   ~~^~~~~~~~~~~~
count_triplets.cpp:152:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < dp1.size(); j++) FinalAns += 2LL * (long long)(dp1.size() - 1) * ((long long)dp1.size() - 1) * dp1[j];
                   ~~^~~~~~~~~~~~
count_triplets.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < dp2.size(); j++) FinalAns += 2LL * (long long)(dp1.size()) * dp2[j];
                   ~~^~~~~~~~~~~~
count_triplets.cpp:155:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   long long X = 0; for (int j = 0; j < dp4.size(); j++) X += dp4[j];
                                    ~~^~~~~~~~~~~~
count_triplets.cpp:157:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < dp4.size(); j++) X -= dp4[j] * dp4[j];
                   ~~^~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:218: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:220: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