Submission #387831

#TimeUsernameProblemLanguageResultExecution timeMemory
387831milleniumEeeeDuathlon (APIO18_duathlon)C++14
36 / 100
835 ms1048580 KiB
#include <bits/stdc++.h> #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define pii pair<int, int> #define fr first #define sc second #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define mk make_pair #define int long long using namespace std; const int MAXN = (int)1e5 + 5; vector <int> g[MAXN]; int n, m; int S, C, F; bool used[MAXN]; bool dfs(int v) { used[v] = 1; if (v == F) { used[v] = 0; if (!used[C]) { return false; } else { return true; } } bool found = false; for (int to : g[v]) { if (!used[to]) { found |= dfs(to); if (found) { used[v] = 0; return true; } } } used[v] = 0; return false; } void subtask1() { int ans = 0; for (int s = 1; s <= n; s++) { for (int c = 1; c <= n; c++) { for (int f = 1; f <= n; f++) { if (s != c && s != f && c != f) { S = s; C = c; F = f; if (dfs(s)) { ans++; } } } } } cout << ans << endl; exit(0); } bool cycle(int v, int par = -1) { used[v] = 1; bool f = 0; for (int to : g[v]) { if (to == par) { continue; } if (!used[to]) { f |= cycle(to, v); } else if (used[to]) { f = 1; } } return f; } bool us[MAXN]; void get_sz(int v, int &sz) { us[v] = 1; sz++; for (int to : g[v]) { if (!us[to]) { get_sz(to, sz); } } } void subtask3() { for (int i = 1; i <= n; i++) { if (szof(g[i]) > 2) { return; } } vector <pii> vec; for (int i = 1; i <= n; i++) { if (!us[i]) { int sz = 0; get_sz(i, sz); vec.pb({cycle(i), sz}); } } int ans = 0; for (pii el : vec) { int cycle = el.fr; int sz = el.sc; if (sz < 3) { continue; } if (cycle) { ans += sz * (sz - 1) * (sz - 2); } else { int sum = 0; for (int i = 1; i <= sz; i++) { sum += (i - 1) * (sz - i) * 2; } ans += sum; } } cout << ans << endl; exit(0); } int sub[MAXN]; void precalc(int v, int par) { sub[v] = 1; used[v] = 1; for (int to : g[v]) { if (to == par) { continue; } precalc(to, v); sub[v] += sub[to]; } } int tree_ans = 0; void calc(int v, int par, int root) { vector <int> vec; for (int to : g[v]) { if (to != par) { calc(to, v, root); vec.pb(sub[to]); } } int sum = 0; vec.pb(sub[root] - sub[v]); int before = 0; for (int i = 0; i < szof(vec); i++) { sum += vec[i] * before; before += vec[i]; } tree_ans += sum * 2; } void solve_for_tree() { for (int i = 1; i <= n; i++) { if (!used[i]) { precalc(i, -1); calc(i, -1, i); } } cout << tree_ans << endl; exit(0); } signed main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } // могут быть несколько компонент if (n <= 10 && m <= 100) { subtask1(); } subtask3(); solve_for_tree(); } /* 12 2 12 11 9 11 */
#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...