제출 #171488

#제출 시각아이디문제언어결과실행 시간메모리
171488VEGAnn관광지 (IZhO14_shymbulak)C++14
100 / 100
152 ms20088 KiB
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() #define sz(x) ((int)x.size()) #define PB push_back #define MP make_pair #define ft first #define sd second #define pll pair<ll, ll> using namespace std; typedef long long ll; const ll OO = 1e18; const int N = 200100; const int M = 1010; const int big = 1e8; //const int PW = (1 << N); vector<int> vc, g[N], cyc; int mrk[N], n, mx1[N], mx2[N], kl1[N], kl2[N], ans = -1, m, mm, pos[N]; ll st[4 * N], psh[4 * N]; ll kans = 0, kol[4 * N]; bool in_cyc[N]; void CYCLE(int lst){ cyc.clear(); int it = sz(vc) - 1; while (1){ cyc.PB(vc[it]); in_cyc[vc[it]] = 1; if (vc[it] == lst) break; it--; } } void dfs(int v, int p){ if (sz(cyc) > 0) return; vc.PB(v); mrk[v] = 1; for (int u : g[v]){ if (u == p) continue; if (mrk[u] == 0) dfs(u, v); else if (mrk[u] == 1) CYCLE(u); } mrk[v] = 2; vc.pop_back(); } void calc_max(int v, int p){ mx1[v] = 0; mx2[v] = -1; kl1[v] = 1; kl2[v] = 0; int ko = 1; ll res = 0, sm = 0; for (int u : g[v]){ if (u == p || in_cyc[u]) continue; calc_max(u, v); if (mx1[v] == mx1[u] + 1){ kl1[v] += kl1[u]; ko++; res += sm * ll(kl1[u]); sm += kl1[u]; } else if (mx1[v] < mx1[u] + 1){ swap(kl1[v], kl2[v]); swap(mx1[v], mx2[v]); kl1[v] = kl1[u]; ko = 1; res = 0; sm = kl1[u]; mx1[v] = mx1[u] + 1; } else if (mx2[v] == mx1[u] + 1){ kl2[v] += kl1[u]; } else if (mx2[v] < mx1[u] + 1) { kl2[v] = kl1[u]; mx2[v] = mx1[u] + 1; } } if (mx1[v] < 1) return; if (ko > 1){ if (mx1[v] + mx1[v] > ans){ ans = mx1[v] + mx1[v]; kans = 0; } if (mx1[v] + mx1[v] == ans) kans += res * 2; } else { if (mx1[v] + mx2[v] > ans){ ans = mx1[v] + mx2[v]; kans = 0; } if (mx1[v] + mx2[v] == ans) kans += ll(kl1[v]) * ll(kl2[v]) * 2; } } void build(int v, int l, int r){ psh[v] = 0; if (l == r){ st[v] = mx1[cyc[l]] + min(l, m - l); kol[v] = kl1[cyc[l]]; return; } int md = (l + r) >> 1; build(v + v, l, md); build(v + v + 1, md + 1, r); st[v] = max(st[v + v], st[v + v + 1]); kol[v] = 0; if (st[v] == st[v + v]) kol[v] += kol[v + v]; if (st[v] == st[v + v + 1]) kol[v] += kol[v + v + 1]; } void push(int v){ if (psh[v] != 0){ st[v] += psh[v]; if (v + v + 1 < 4 * n){ psh[v + v] += psh[v]; psh[v + v + 1] += psh[v]; } psh[v] = 0; } } void update(int v, int tl, int tr, int l, int r, int vl){ push(v); if (l > r) return; if (tl == l && tr == r){ psh[v] += vl; push(v); return; } int md = (tl + tr) >> 1; update(v + v, tl, md, l, min(r, md), vl); update(v + v + 1, md + 1, tr, max(l, md + 1), r, vl); st[v] = max(st[v + v], st[v + v + 1]); kol[v] = 0; if (st[v] == st[v + v]) kol[v] += kol[v + v]; if (st[v] == st[v + v + 1]) kol[v] += kol[v + v + 1]; } void upd(int l, int r, int vl){ if (l < 0){ update(1, 0, m - 1, 0, r, vl); update(1, 0, m - 1, m + l, m - 1, vl); } else if (r >= m){ update(1, 0, m - 1, l, m - 1, vl); update(1, 0, m - 1, 0, r - m, vl); } else { update(1, 0, m - 1, l, r, vl); } } void PUSH(int v, int l, int r){ push(v); if (l == r) return; int md = (l + r) >> 1; PUSH(v + v, l, md); PUSH(v + v + 1, md + 1, r); st[v] = max(st[v + v], st[v + v + 1]); kol[v] = 0; if (st[v] == st[v + v]) kol[v] += kol[v + v]; if (st[v] == st[v + v + 1]) kol[v] += kol[v + v + 1]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("penguins.in","r",stdin); freopen("penguins.out","w",stdout); // freopen("in.txt","r",stdin); cin >> n; for (int i = 0; i < n; i++){ int x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); } dfs(0, -1); for (int it = 0; it < sz(cyc); it++){ int cr = cyc[it]; pos[cr] = it; calc_max(cr, -1); } bool good = (sz(cyc) % 2 == 0); m = sz(cyc); mm = m / 2; build(1, 0, m - 1); for (int it = 0; it < m; it++){ int v = cyc[it]; if (it > 0){ upd(it - mm, it - 1, +1); upd(it, it + mm - 1, -1); } update(1, 0, m - 1, it, it, -big); // PUSH(1, 0, m - 1); ll mdst = st[1] + mx1[v]; if (mdst > ans){ ans = mdst; kans = 0; } if (mdst == ans) kans += ll(kl1[v]) * kol[1]; if (good){ int op = cyc[(it + mm) % m]; if (mm + mx1[op] + mx1[v] == ans) kans += ll(kl1[op]) * ll(kl1[v]); } update(1, 0, m - 1, it, it, +big); } // for (int i1 = 0; i1 < sz(cyc); i1++) // for (int i2 = i1 + 1; i2 < sz(cyc); i2++){ // int dst = i2 - i1, n1 = cyc[i1], n2 = cyc[i2]; // dst = min(dst, sz(cyc) - dst); // dst += mx1[n1] + mx1[n2]; // // if (dst > ans){ // ans = dst; // kans = 0; // } // // if (dst == ans) // kans += ll(kl1[n1]) * ll(kl1[n2]); // // if (good && (i2 - i1) == (sz(cyc) >> 1) && dst == ans) // kans += ll(kl1[n1]) * ll(kl1[n2]); // } cout << kans / 2 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...