Submission #103247

#TimeUsernameProblemLanguageResultExecution timeMemory
103247E869120Duathlon (APIO18_duathlon)C++14
47 / 100
636 ms40852 KiB
#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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...