| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 343380 | apostoldaniel854 | Shymbulak (IZhO14_shymbulak) | C++14 | 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;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;
/**
- we have a single cycle in this graph
- we calculate the maximum depth and its count in every tree spanning from the cycle
- we use a segmentree on a cyclic vector (we will double it)
- now we solve independently for every tree spaning from the cycle
**/
const int MAX_N = 2e5;
vector <int> cycle;
int state[1 + MAX_N];
bool fixed[1 + MAX_N];
void dfs_cycle (int node, int par) {
state[node] = 1;
v.pb (node);
for (int vec : gr[node])
if (vec != par) {
if (state[vec] == 0)
dfs_cycle (vec, node);
else if (state[vec] == 1) {
while (v.back () != vec) {
cycle.pb (v.back ());
v.pop_back ();
}
cycle.pb (vec);
}
}
v.pop_back ();
state[node] = 2;
}
struct Node {
int value;
int cnt;
};
Node max_depth[1 + MAX_N];
Node ans;
Node join (Node l, Node r) {
Node x;
x = l;
if (x.value == r.value)
x.cnt += r.cnt;
else if (x.value < r.value)
x = r;
return x;
}
void dfs_depth (int node, int par) {
max_depth[node] = {0, 1};
for (int son : gr[node])
if (son != par && not fixed[son]) {
dfs_depth (son, node);
upd_ans (max_depth[node], {max_depth[son].value + 1, max_depth[son].cnt});
upd_ans (ans, {max_depth[node].value + max_depth[son].value + 1, max_depth[node].cnt * max_depth[son].cnt});
}
}
struct LazySegTree {
vector <Node> seg;
vector <int> lazy;
int n;
LazySegTree (int n) {
this->n = n;
seg.resize (1 + 4 * n);
lazy.resize (1 + 4 * n);
}
void push (int node) {
if (lazy[node]) {
int left_node = node * 2, right_node = node * 2 + 1;
seg[left_node].value += lazy[node];
seg[right_node].value += lazy[node];
lazy[left_node] += lazy[node];
lazy[right_node] += lazy[node];
lazy[node] = 0;
}
}
void build (int node, int lb, int rb, vector <pair <int, int>> &v) {
if (lb == rb) {
seg[node] = {v[lb - 1].first + lb - 1, v[lb - 1].second};
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
build (left_node, lb, mid, v);
build (right_node, mid + 1, v);
seg[node] = join (seg[left_node], seg[right_node]);
}
void update (int node, int lb, int rb, int q_left, int q_right, int to_add) {
if (q_left <= lb && rb <= q_right) {
seg[node].value += to_add;
lazy[node] += to_add;
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
push (node);
if (q_left <= mid)
update (left_node, lb, mid, q_left, q_right, to_add);
if (q_right >= mid + 1)
update (right_node, mid + 1, rb, q_left, q_right, to_add);
seg[node] = join (seg[left_node], seg[right_node]);
}
Node query (int node, int lb, int rb, int q_left, int q_right) {
if (q_left <= lb && rb <= q_right)
return seg[node];
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
push (node);
Node ans = {0, 0};
if (q_left <= mid)
ans = join (ans, query (left_node, lb, mid, q_left, q_right));
if (q_right >= mid + 1)
ans = join (ans, query (right_node, mid + 1, rb, q_left, q_right));
return ans;
}
};
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
gr[x].pb (y);
gr[y].pb (x);
}
dfs_cycle (1, 0);
for (int x : cycle)
fixed[x] = true;
for (int x : cycle)
dfs_depths (x, 0);
vector <int> elements;
for (int x : cycle)
elements.pb (max_depth[x]);
for (int x : cycle)
elements.pb (max_depth[x]);
int m = cycle.size ();
int sz = elements.size ();
LazySegTree helper (sz);
helper.build (1, 1, sz, elements);
for (int i = 1; i <= m; i++) {
Node l = helper.query (1, 1, sz, i);
}
return 0;
}