Submission #387988

#TimeUsernameProblemLanguageResultExecution timeMemory
387988milleniumEeeeDuathlon (APIO18_duathlon)C++14
23 / 100
1098 ms34940 KiB
#include <bits/stdc++.h> #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define int long long using namespace std; const int MAXN = (int)1e5 + 5; vector <int> g[MAXN]; vector <int> G[MAXN]; // кактусовый граф int pr[MAXN]; bool used[MAXN]; bool black[MAXN]; vector <int> cycle[MAXN]; int ind[MAXN], cur_ind; pii joop(int x, int y) { if (x > y) { swap(x, y); } return {x, y}; } void precalc(int v, int par) { pr[v] = par; used[v] = 1; for (int to : g[v]) { if (to == par) { continue; } if (used[to] && !black[to]) { cur_ind++; int fn = v; while (fn != to) { cycle[cur_ind].pb(fn); fn = pr[fn]; } cycle[cur_ind].pb(fn); for (int el : cycle[cur_ind]) { black[el] = 1; ind[el] = cur_ind; } } else if (!used[to]) { precalc(to, v); } } } int ans = 0; int sub[MAXN]; int n, m; int root; // корень сжатого дерева bool was[MAXN]; void calc_sub(int v, int par) { was[ind[v]] = 1; sub[v] = szof(cycle[ind[v]]); for (int to : G[v]) { if (to == par) { continue; } calc_sub(to, v); sub[v] += sub[to]; } } int get_mult(vector <int> &vec) { int res = 0; int before = 0; for (int el : vec) { res += before * el; before += el; } return res * 2; } void calc_ans(int v, int par) { int before_ans = ans; auto calc_other = [&]() { vector <int> vec; for (int to : G[v]) { if (to == par) { continue; } vec.pb(sub[to]); } if (v != root) { vec.pb(sub[root] - sub[v]); } int sum = 0; int before = 0; for (int el : vec) { sum += before * el; before += el; } return sum * 2; }; if (!black[v]) { ans += calc_other(); } else { //assert(false); auto calc_my = [&](int vrt) { int my = 0; for (int to : g[vrt]) { if (ind[vrt] != ind[to]) { int need = cycle[ind[to]][0]; if (need == par) { my += n - sub[v]; } else { my += sub[need]; } } } return my; }; auto have = [&](int v) { bool flag = (szof(g[v]) > 2); return flag; }; // 1 in cycle { int kek = 0; vector <int> vec; for (int vrt : cycle[ind[v]]) { if (have(vrt)) { vec.pb(calc_my(vrt)); } } int before = 0; for (int el : vec) { kek += el * before; before += el; } kek *= 2; int here1 = 0; bool flag = (v == 7); for (int c : cycle[ind[v]]) { if (!have(c)) { ans += kek; here1 += kek; if (flag) { //cout << "no " << c << " " << kek << endl; } } else { vector <int> my_sub; for (int to : g[c]) { if (ind[to] != ind[c]) { int need = cycle[ind[to]][0]; if (need == par) { my_sub.pb(sub[root] - sub[v]); } else { my_sub.pb(sub[need]); } } } ans += kek + get_mult(my_sub); here1 += kek + get_mult(my_sub); if (flag) { //cout << "yes " << c << " " << kek + get_mult(my_sub) << endl; } } } if (v == 7) { //cout << "here1: " << here1 << endl; } } // 2 in cycle { int here2 = 0; int other = n - szof(cycle[ind[v]]); int cycle_size = szof(cycle[ind[v]]); for (int c : cycle[ind[v]]) { for (int s : cycle[ind[v]]) { if (c != s) { ans += (other - calc_my(s)) * 2; here2 += (other - calc_my(s)) * 2; } } } if (v == 6) { //cout << "here2: " << here2 << endl; } } // 3 in cycle { int siz = szof(cycle[ind[v]]); ans += siz * (siz - 1) * (siz - 2); if (v == 6) { //cout << "here3: " << siz * (siz - 1) * (siz - 2) << endl; } } } //cout << v << ": " << ans - before_ans << endl; for (int to : G[v]) { if (to == par) { continue; } calc_ans(to, v); } } signed main() { fastInp; cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } for (int i = 1; i <= n; i++) { if (!used[i]) { precalc(i, -1); } } for (int i = 1; i <= n; i++) { if (!black[i]) { ind[i] = ++cur_ind; cycle[ind[i]].pb(i); } } set <pii> st; for (int i = 1; i <= n; i++) { for (int to : g[i]) { if (ind[i] != ind[to]) { st.insert(joop(ind[i], ind[to])); } } } for (auto el : st) { int x = cycle[el.fr][0]; int y = cycle[el.sc][0]; G[x].pb(y); G[y].pb(x); } for (int i = 1; i <= cur_ind; i++) { root = cycle[i][0]; if (!was[ind[root]]) { calc_sub(root, -1); calc_ans(root, -1); } } cout << ans << endl; } /* 8 9 6 2 6 7 6 8 7 8 8 1 8 4 4 3 4 5 5 3 */

Compilation message (stderr)

count_triplets.cpp: In function 'void calc_ans(long long int, long long int)':
count_triplets.cpp:180:8: warning: unused variable 'cycle_size' [-Wunused-variable]
  180 |    int cycle_size = szof(cycle[ind[v]]);
      |        ^~~~~~~~~~
count_triplets.cpp:87:6: warning: unused variable 'before_ans' [-Wunused-variable]
   87 |  int before_ans = ans;
      |      ^~~~~~~~~~
#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...