Submission #1190242

#TimeUsernameProblemLanguageResultExecution timeMemory
1190242omsincoconutDuathlon (APIO18_duathlon)C++17
0 / 100
67 ms30144 KiB
/* Do 2-edge connectivity => Get condensation tree If s, c, f all in different components Imagine the condensation tree having the vertices' weights = number of vertex in that component Fix the position of c, it is easy to calculate the number of possible (s, f) If s, c, f all in same components For each component with n vertices, add n(n-1)(n-2) If s, c in same component but f in different We can have any (s, c, f) except if s is on the path fron c to f. It is easier to subtract out that case. */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5+5; ll n, m; vector<int> edge[MAXN]; int p[MAXN], tin[MAXN], low[MAXN]; void dfs(int u) { static int ct = 1; low[u] = tin[u] = ct++; for (int v : edge[u]) { if (tin[v] == -1) { p[v] = u; dfs(v); } if (p[u] != v) low[u] = min(low[v], low[u]); } } vector<int> lowlist; vector<int> comp[MAXN]; vector<int> treeedge[MAXN]; ll dp[MAXN]; vector<int> treechild[MAXN]; int treep[MAXN]; void treedfs(int u) { dp[u] = comp[u].size(); for (int v : treeedge[u]) { if (dp[v] != -1) continue; treechild[u].push_back(v); treep[v] = u; treedfs(v); dp[u] += dp[v]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; edge[u].push_back(v); edge[v].push_back(u); } fill(tin, tin+n+1, -1); fill(p, p+n+1, -1); p[1] = 1; dfs(1); for (int i = 1; i <= n; i++) { lowlist.push_back(low[i]); comp[low[i]].push_back(i); } sort(lowlist.begin(), lowlist.end()); lowlist.resize(unique(lowlist.begin(), lowlist.end()) - lowlist.begin()); for (int u = 1; u <= n; u++) { for (int v : edge[u]) { if (low[u] != low[v]) { treeedge[low[u]].push_back(low[v]); } } } fill(dp, dp+n+1, -1); treep[lowlist[0]] = lowlist[0]; treedfs(lowlist[0]); // Case 1 ll case1 = 0; for (int i : lowlist) { ll sm = 0, nans = 0; for (int j : treechild[i]) { nans += dp[j]*sm; sm += dp[j]; } nans += (n-dp[i])*sm; case1 += nans*(ll)(comp[i].size())*2; } // Case 2 ll case2 = 0; for (int i : lowlist) { ll sz = comp[i].size(); case2 += sz*(sz-1)*(sz-2); } // Case 3 ll case3 = 0; for (int i : lowlist) { ll sz = comp[i].size(); for (int j : treechild[i]) { case3 += (sz-1)*(sz-1)*dp[j]; } case3 += (sz-1)*(sz-1)*(n-dp[i]); } cout << case1 + case2 + 2*case3; return 0; } /* 4 4 1 2 2 3 3 4 4 2 */
#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...