#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;
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);
}
// 総計算
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 < dp1.size(); j++) X += dp1[j];
X *= X;
for (int j = 0; j < dp1.size(); j++) X -= dp1[j] * dp1[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 <= 0 && M <= 100) {
cout << solve_subtask2() << endl;
}
else {
cout << solve_subtask7() << endl;
}
return 0;
}
Compilation message
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:147: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:148: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:149: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:151:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
long long X = 0; for (int j = 0; j < dp1.size(); j++) X += dp1[j];
~~^~~~~~~~~~~~
count_triplets.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < dp1.size(); j++) X -= dp1[j] * dp1[j];
~~^~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:214: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:216: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
605 ms |
40620 KB |
Output is correct |
| 2 |
Correct |
607 ms |
40736 KB |
Output is correct |
| 3 |
Incorrect |
515 ms |
37356 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
487 ms |
34440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
444 ms |
34364 KB |
Output is correct |
| 2 |
Incorrect |
519 ms |
34328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
