| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 68572 | cdemirer | Shymbulak (IZhO14_shymbulak) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
int N;
vvi edges;
vi circle;
bool onCircle[200000] = {0};
vvi distantNodes;
vi distantDist;
vi distantSize;
int parent[200000];
bool vis[200000] = {0};
void fcircle(int x) {
vis[x] = true;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (vis[y]) {
int q = x;
while (q != y) {
circle.pb(q);
q = parent[q];
}
circle.pb(y);
return;
}
parent[y] = x;
fcircle(y);
if (!circle.empty()) break;
}
}
int fdistance(int x) {
int ret = 0;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (onCircle[y]) continue;
parent[y] = x;
ret = max(ret, 1 + fdistance(y));
}
return ret;
}
int fsize(int x, int dst) {
if (dst == 0) return 1;
int ret = 0;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (onCircle[y]) continue;
parent[y] = x;
ret += fsize(y, dst-1);
}
return ret;
}
typedef struct NodeT {
int llim, rlim;
int value, valsz, up;
} Node;
const int segsz = 524288;
const int offset = segsz/2;
Node seg[segsz];
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
void seginit() {
for (int i = offset; i < segsz; i++) {
seg[i].llim = seg[i].rlim = i-offset;
seg[i].value = 0;
}
for (int i = offset-1; i > 0; i--) {
seg[i].llim = seg[left(i)].llim;
seg[i].rlim = seg[right(i)].rlim;
seg[i].value = 0;
}
}
// setPointWithSecondValue --> Can be used only before any normal update calls
void setPointWithSecondValue(int pos, int val1, int val2) {
pos += offset;
seg[pos].value = val1;
seg[pos].valsz = val2;
pos /= 2;
while (pos) {
int mx = max(seg[left(pos)].value, seg[right(pos)].value);
int sz = 0;
if (seg[left(pos)].value == mx) sz += seg[left(pos)].valsz;
if (seg[right(pos)].value == mx) sz += seg[right(pos)].valsz;
seg[pos].value = mx;
seg[pos].valsz = sz;
pos /= 2;
}
}
void push(int x) {
seg[x].value += seg[x].up;
if (x < offset) {
seg[left(x)].up += seg[x].up;
seg[right(x)].up += seg[x].up;
}
seg[x].up = 0;
}
ii get(int x, int l, int r) {
push(x);
int llim = seg[x].llim, rlim = seg[x].rlim;
int mid = (llim+rlim)/2;
if (l == llim && r == rlim) return mp(seg[x].value, seg[x].valsz);
else if (l > mid) return get(right(x), l, r);
else if (r <= mid) return get(left(x), l, r);
else {
ii a = get(left(x), l, mid);
ii b = get(right(x), mid+1, r);
int mx = max(a.first, b.first);
int sz = 0;
if (a.first == mx) sz += a.second;
if (b.first == mx) sz += b.second;
return mp(mx, sz);
}
}
void update(int x, int l, int r, int u) {
push(x);
int llim = seg[x].llim, rlim = seg[x].rlim;
int mid = (llim+rlim)/2;
if (l == llim && r == rlim) {
seg[x].up += u;
push(x);
return;
}
else if (l > mid) update(right(x), l, r, u);
else if (r <= mid) update(left(x), l, r, u);
else {
update(left(x), l, mid, u);
update(right(x), mid+1, r, u);
}
ii a = get(left(x), llim, mid);
ii b = get(right(x), mid+1, rlim);
int mx = max(a.first, b.first);
int sz = 0;
if (a.first == mx) sz += a.second;
if (b.first == mx) sz += b.second;
seg[x].value = mx;
seg[x].valsz = sz;
}
void debugpush(int x) {
push(x);
if (x < offset) {
debugpush(left(x));
debugpush(right(x));
} else {
seg[x].value += seg[x].up;
seg[x].up = 0;
}
}
ll dfsanswer = -1;
ll dfsanswersize = 0;
ll dp[200000][2];
void dfs(int x) {
vii childs;
ll q;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (onCircle[y]) continue;
parent[y] = x;
dfs(y);
childs.pb(mp(dp[y][0], dp[y][1]));
q = y;
}
if (childs.size() == 0) {
dp[x][0] = 1;
dp[x][1] = 1;
}
else if (childs.size() == 1) {
dp[x][0] = dp[q][0] + 1;
dp[x][1] = dp[q][1];
}
else {
sort(childs.begin(), childs.end());
reverse(childs.begin(), childs.end());
int mx = childs[0].first;
int mx2 = -1;
for (int i = 0; i < childs.size(); i++) {
if (childs[i].first != mx) mx2 = max(mx2, childs[i].first);
}
ll ans = 0;
ll presz = 0;
for (int i = 0; i < childs.size(); i++) {
int y = childs[i];
if (mx == dp[y][0]) {
ans += presz * dp[y][0];
presz += dp[y][0];
}
}
int len;
if (!ans) {
for (int i = 0; i < childs.size(); i++) {
int y = childs[i];
if (mx2 == dp[y][0]) {
ans += presz * dp[y][0];
}
}
len = mx + mx2;
}
else {
len = mx + mx;
}
if (len == dfsanswer) {
dfsanswersize += ans;
} else if (len > dfsanswer) {
dfsanswer = len;
dfsanswersize = ans;
}
dp[x][0] = mx;
dp[x][1] = presz;
}
}
llp solveTree(int st) {
parent[st] = -1;
dfs(st);
return mp(dp[st][0], dp[st][1]);
}
int main(int argc, char **argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N; edges.resize(N);
for (int i = 0; i < N; i++) {
int a, b; cin >> a >> b; a--; b--;
edges[a].pb(b); edges[b].pb(a);
}
parent[0] = -1;
fcircle(0);
for (int i = 0; i < circle.size(); i++) onCircle[circle[i]] = true;
int circlen = circle.size();
distantDist.resize(circle.size());
distantSize.resize(circle.size());
for (int i = 0; i < circle.size(); i++) {
parent[circle[i]] = -1;
distantDist[i] = fdistance(circle[i]);
parent[circle[i]] = -1;
distantSize[i] = fsize(circle[i], distantDist[i]);
}
seginit();
for (int i = 0; i < circle.size(); i++) {
//update(1, i, i, distantDist[i] + min(i, circlen-i));
setPointWithSecondValue(i, distantDist[i] + min(i, circlen-i), distantSize[i]);
}
/*for (int i = 0; i < circle.size(); i++) {
cerr << circle[i] << " ";
} cerr << endl;
for (int i = 0; i < circle.size(); i++) {
//cerr << seg[offset+i].value << " ";
cerr << distantDist[i] << " ";
} cerr << endl;
for (int i = 0; i < circle.size(); i++) {
//cerr << seg[offset+i].value << " ";
cerr << distantSize[i] << " ";
} cerr << endl;
cerr << endl;*/
/*cerr << "the initial segment:" << endl;
for (int i = 0; i < circle.size(); i++) {
cerr << seg[offset+i].value << " ";
//cerr << distantDist[i] << " ";
} cerr << endl;*/
vector<ll> ans(circle.size());
vi selected(circle.size());
for (int i = 0; i < circle.size(); i++) {
/*cerr << "i is: " << i << " and this is how the segment currently is:" << endl;
debugpush(1); for (int i = 0; i < circle.size(); i++) {
cerr << seg[offset+i].value << " ";
} cerr << endl;*/
if (circlen % 2 == 0) {
int oppo = (i+circlen/2)%circlen;
int ex1 = i;
int ex2 = oppo;
if (ex1 > ex2) swap(ex1, ex2);
ii a = (ex1 != 0 ? get(1, 0, ex1-1) : mp(0, 0));
ii b = (ex2-ex1>1 ? get(1, ex1+1, ex2-1) : mp(0, 0));
ii c = (ex2 != circlen-1 ? get(1, ex2+1, circlen-1) : mp(0, 0));
int maxfst = max(a.first, max(b.first, c.first));
int sz = 0;
if (a.first == maxfst) sz += a.second;
if (b.first == maxfst) sz += b.second;
if (c.first == maxfst) sz += c.second;
ii o = get(1, oppo, oppo);
if (maxfst >= o.first) {
selected[i] = maxfst;
ans[i] += (ll)distantSize[i]*(ll)sz;
}
if (o.first >= maxfst) {
selected[i] = o.first;
ans[i] += (ll)distantSize[i]*(ll)o.second*(2ll);
}
} else { // circlen % 2 == 1
ii a = (i?get(1, 0, i-1):mp(0, 0));
ii b = (i!=circlen-1?get(1, i+1, circlen-1):mp(0, 0));
int maxfst = max(a.first, b.first);
int sz = 0;
if (a.first == maxfst) sz += a.second;
if (b.first == maxfst) sz += b.second;
selected[i] = maxfst;
ans[i] = (ll)distantSize[i]*(ll)sz;
}
selected[i] += distantDist[i];
/*cerr << "selected is set: " << selected[i] << endl;
cerr << "ans is set: " << ans[i] << endl;
cerr << endl;*/
if (circlen % 2 == 0) {
update(1, 0, circlen-1, 1);
int l = i+1, r = i+circlen/2;
if (r < circlen) {
update(1, l, r, -2);
} else if (l >= circlen) {
l -= circlen, r -= circlen;
update(1, l, r, -2);
} else {
update(1, l, circlen-1, -2);
r -= circlen;
update(1, 0, r, -2);
}
} else { // circlen % 2 == 1
update(1, 0, circlen-1, 1);
int l = i+1, r = i+circlen/2;
if (r < circlen) {
update(1, l, r, -2);
} else if (l >= circlen) {
l -= circlen, r -= circlen;
update(1, l, r, -2);
} else {
update(1, l, circlen-1, -2);
r -= circlen;
update(1, 0, r, -2);
}
int x = i+circlen/2+1;
if (x >= circlen) x -= circlen;
update(1, x, x, -1);
}
}
/*cerr << "the last of the segment:" << endl;
debugpush(1); for (int i = 0; i < circle.size(); i++) {
cerr << seg[offset+i].value << " ";
} cerr << endl;*/
int mxs = *(max_element(selected.begin(), selected.end()));
ll answer = 0;
for (int i = 0; i < circle.size(); i++) if (selected[i] == mxs) answer += ans[i];
answer /= 2;
/*for (int i = 0; i < circle.size(); i++) {
cerr << selected[i] << " ";
} cerr << endl;
for (int i = 0; i < circle.size(); i++) {
cerr << ans[i] << " ";
} cerr << endl;*/
// don't forget to check the furthest pairs inside one circle piece
for (int i = 0; i < circle.size(); i++) {
onCircle[circle[i]] = false;
llp res = solveTree(circle[i]);
if (res.first > mxs) {
mxs = res.first;
answer = res.second;
} else if (res.first == mxs) {
answer += res.second;
}
onCircle[circle[i]] = true;
}
cout << answer << endl;
return 0;
}