Submission #343041

#TimeUsernameProblemLanguageResultExecution timeMemory
343041SprdaloShymbulak (IZhO14_shymbulak)C++17
0 / 100
12 ms1644 KiB
#include <bits/stdc++.h> using namespace std; #define int ll typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<double> vd; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<string> vs; typedef vector<pi> vp; typedef vector<pl> vpl; const int maxn = 5010; vi e[maxn], cyc(maxn), vis(maxn); stack<int> st; bool ciklus = 0; int len; void stek(int x){ ciklus = 1; while(!st.empty()){ cyc[st.top()] = 1; ++len; if (st.top() == x) break; st.pop(); } } void cycle(int x, int start){ vis[x] = 1; st.push(x); for (int y : e[x]){ if (start == y) continue; if (vis[y]){ stek(y); break; } cycle(y, x); if (ciklus) break; } if (ciklus) return; st.pop(); } vi a(maxn, -1), s(maxn); int poc; void calc(int x, int st, int d = 0){ if (d > a[poc]){ a[poc] = d; s[poc] = 1; } else if (d == a[poc]){ s[poc]++; } for (int i : e[x]) if (i != st && !cyc[i]) calc(i, x, d+1); } int sol, cnt; void update(int res, int cc){ if (res == sol) cnt += cc; if (res > sol){ sol = res; cnt = cc; } } void solve(int x, int st, int d = 0){ if (x != st){ int res = d + a[poc] + a[x], cc = s[poc] * s[x]; update(res, cc); } for (int i : e[x]) if (i != st && cyc[i] && 2 * (d+1) <= len) solve(i, x, d+1); } int d, cc; void unutra(int x, int st, int dist = 1){ if (dist == d) ++cc; if (dist > d){ d = dist; cc = 1; } for (int y : e[x]){ if (y != st) unutra(y, x, dist+1); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; ++i){ int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } cycle(1, 1); for (int i = 1; i <= n; ++i){ if (!cyc[i]) continue; poc = i; calc(i, i); } for (int i = 1; i <= n; ++i){ if (cyc[i]){ poc = i; solve(i,i); } } int test = 0; for (int i = 1; i <= n; ++i){ if (!cyc[i]) continue; vp t; for (int j : e[i]){ if (cyc[j]) continue; d = 0; cc = 0; unutra(j, i); t.push_back({d, cc}); } sort(t.rbegin(), t.rend()); if (t.empty()) continue; int sz = t.size(); if (sz == 1){ update(t[0].first, t[0].second*2); continue; } int br = 0, u = t[1].second; for (int j = 2; j < sz; ++j){ if (t[j].first != t[1].first) break; ++br; u += t[j].second; } if (t[0].first == t[1].first){ int g = 0; u += t[0].second; for (int j = 0; j < sz; ++j){ if (t[j].first != t[0].first) break; g += (u - t[j].second) * t[j].second; } int ta = sol, tb= cnt; update(t[0].first*2, g); if (sol != ta || cnt != tb) test = 1; continue; } int ta = sol, tb = cnt; update(t[0].first + t[1].first, u * t[0].second*2); if (ta != sol || tb != cnt) test=2; } if (test==2) throw SIGSEGV; cout << cnt/2 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...