Submission #742806

#TimeUsernameProblemLanguageResultExecution timeMemory
742806becaidoDuathlon (APIO18_duathlon)C++17
31 / 100
185 ms50336 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> using namespace std; #ifdef WAIMAI #define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE) void dout() {cout << '\n';} template<typename T, typename...U> void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);} #else #define debug(...) 7122 #endif #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back #define F first #define S second const int SIZE = 2e5 + 5; int n, m; ll ans; bool vs[SIZE]; int gn, sz[SIZE]; vector<int> adj[SIZE], gadj[SIZE]; ll P(int x, int y) { if (y < 0 || y > x) return 0; if (y == 2) return 1ll * x * (x - 1); if (y == 3) return 1ll * x * (x - 1) * (x - 2); } struct VBCC { // need adj int n, dfcnt = 0, bccnt = 0; vector<int> dfn, low, st; vector<vector<int>> bcc; VBCC() {} VBCC(int n) : n(n) { dfn = low = vector<int>(n + 1, 0); bcc = vector<vector<int>>(n + 1, vector<int>()); } void tarjan(int pos, int fa) { dfn[pos] = low[pos] = ++dfcnt; st.emplace_back(pos); for (int np : adj[pos]) { if (np != fa) { if (dfn[np] == 0) { tarjan(np, pos); low[pos] = min(low[pos], low[np]); if (dfn[pos] <= low[np]) { bccnt++; while (1) { int x = st.back(); bcc[x].emplace_back(bccnt); st.pop_back(); if (x == np) { break; } } bcc[pos].emplace_back(bccnt); } } else { low[pos] = min(low[pos], dfn[np]); } } } if (pos == fa) { st.pop_back(); if (bcc[pos].size() == 0) { bcc[pos].emplace_back(++bccnt); } } } void work() { for (int i = 1; i <= n; i++) { if (dfn[i] == 0) { tarjan(i, i); } } gn = bccnt; FOR (i, 1, n) { if (bcc[i].size() == 1) sz[bcc[i][0]]++; else { sz[++gn] = 1; for (int x : bcc[i]) { gadj[gn].pb(x); gadj[x].pb(gn); } } } FOR (i, 1, gn) if (!vs[i]) { int all = 0; auto pre = [&](auto pre, int pos, int fa)->void { all += sz[pos]; for (int np : gadj[pos]) if (np != fa) pre(pre, np, pos); }; pre(pre, i, i); auto dfs = [&](auto dfs, int pos, int fa)->int { vs[pos] = 1; vector<int> v; int sum = sz[pos]; for (int np : gadj[pos]) if (np != fa) { int w = dfs(dfs, np, pos); sum += w; v.pb(w); } v.pb(all - sum); ans += P(sz[pos], 3); if (pos > bccnt) { for (int np : gadj[pos]) ans += P(sz[np], 2); } for (int x : v) { ans += 2 * P(sz[pos], 2) * x; ans += 1ll * sz[pos] * x * (all - sz[pos] - x); } return sum; }; dfs(dfs, i, i); } } } G; void solve() { cin >> n >> m; while (m--) { int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } G = VBCC(n); G.work(); cout << ans << '\n'; } int main() { Waimai; solve(); }

Compilation message (stderr)

count_triplets.cpp: In function 'long long int P(int, int)':
count_triplets.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^
#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...