제출 #553205

#제출 시각아이디문제언어결과실행 시간메모리
553205tranxuanbach철인 이종 경기 (APIO18_duathlon)C++17
23 / 100
102 ms52080 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (auto i = (l); i < (r); i++) #define ForE(i, l, r) for (auto i = (l); i <= (r); i++) #define FordE(i, l, r) for (auto i = (l); i >= (r); i--) #define Fora(v, a) for (auto v: (a)) #define bend(a) (a).begin(), (a).end() #define isz(a) ((signed)(a).size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pii>; using vvi = vector <vi>; const int N = 5e5 + 5; int n, m; vi adj[N]; int ctrtin = 0, tin[N], low[N]; vi st; int szcpn; int cntbcc = 0; vi adjbcc[N]; void dfs(int u, int p){ tin[u] = low[u] = ++ctrtin; st.emplace_back(u); szcpn++; Fora(v, adj[u]){ if (v == p){ continue; } if (tin[v]){ low[u] = min(low[u], tin[v]); } else{ dfs(v, u); if (low[v] >= tin[u]){ cntbcc++; adjbcc[u].emplace_back(n + cntbcc); do{ int tv = st.back(); st.pop_back(); adjbcc[n + cntbcc].emplace_back(tv); } while (adjbcc[n + cntbcc].back() != v); } } } } ll ans; int sz[N]; void dfs_bcc(int u){ sz[u] = (u <= n); Fora(v, adjbcc[u]){ dfs_bcc(v); sz[u] += sz[v]; if (u > n){ ans -= (ll)isz(adjbcc[u]) * sz[v] * (sz[v] - 1); } } if (u > n){ ans -= (ll)isz(adjbcc[u]) * (szcpn - sz[u]) * (szcpn - sz[u] - 1); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); cin >> n >> m; ForE(i, 1, m){ int u, v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } ForE(u, 1, n){ if (!tin[u]){ szcpn = 0; dfs(u, 0); ans += (ll)szcpn * (szcpn - 1) * (szcpn - 2); dfs_bcc(u); } } cout << ans << endl; } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#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...