oj.uz

Submission #250058

# Submission time Handle Problem Language Result Execution time Memory
250058 2020-07-16T18:34:42 Z srvlt Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 178 ms 30584 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2e5 + 123, inf = 1e8;
int n, used[n0], par[n0], k, c[n0], inc[n0], h[n0];
vector <int> g[n0];

void dfs(int v, int p) {
	used[v] = 1;
	for (int to : g[v]) {
		if (to == p) continue;
		if (used[to] == 1) {
			int u = v;
			while (u != to) {
				c[++k] = u, inc[u] = 1;
				u = par[u];
			}
			c[++k] = to, inc[to] = 1;
		}
		if (used[to] == 0) {
			par[to] = v;
			dfs(to, v);
		}
	}
	used[v] = 2;
}

struct Pair {
	int x, y;
	Pair(int X = 0, int Y = 0) {
		x = X, y = Y;
	}
};

Pair max(const Pair & p1, const Pair & p2) {
	if (p1.x > p2.x) return p1;
	if (p2.x > p1.x) return p2;
	return Pair(p1.x, p1.y + p2.y);
}
Pair b[n0], val[n0];
ll cnt[n0];

void go(int v, int p) {
	b[v] = Pair(h[v], 1);
	for (int to : g[v]) {
		if (inc[to] || to == p) continue;
		h[to] = h[v] + 1;
		go(to, v);
		b[v].x -= 2 * h[v];
		val[to] = max(val[to], b[v]);
		b[v].x += 2 * h[v];
		b[v] = max(b[v], b[to]);
	}
}

void go2(int v, int p) {
	cnt[val[v].x + h[v]] += val[v].y;
	cnt[b[v].x] += b[v].y;
	for (int to : g[v]) {
		if (inc[to] || to == p) continue;
		val[to] = max(val[to], val[v]);
		go2(to, v);
	}
}

struct Node {
	int l = 0, r = 0;
	Pair x, y;
	void clean() {
		x.x = -inf, x.y = 0;
		y.x = -inf, y.y = 0;
	}
	void init() {
		x = Pair(b[c[l]].x + l, b[c[l]].y);
		y = Pair(b[c[l]].x - l, b[c[l]].y);
	}
	void merge(const Node & L, const Node & R) {
		x = max(L.x, R.x);
		y = max(L.y, R.y);
	}
};
Node t[(1 << 19) + 1];

void build(int v, int l, int r) {
	t[v].l = l, t[v].r = r;
	if (l == r) {
		t[v].init();
		return;
	}
	int m = l + r >> 1;
	build(v << 1, l, m), build(v << 1 | 1, m + 1, r);
	t[v].merge(t[v << 1], t[v << 1 | 1]);
}

Node res;
void get(int v, int l, int r) {
	if (t[v].l > r || t[v].r < l) return;
	if (t[v].l >= l && t[v].r <= r) {
		res.merge(res, t[v]);
		return;
	}
	get(v << 1, l, r), get(v << 1 | 1, l, r);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y), g[y].pb(x);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++)
		if (inc[i]) go(i, i);
	for (int i = 1; i <= n; i++)
		if (inc[i]) go2(i, i);
	build(1, 1, k);
	for (int i = 1; i <= k; i++) {
		int l = i + 1, r = min(k, i + k / 2);
		if (l <= r) {
			res.clean(), get(1, l, r);
			cnt[b[c[i]].x - i + res.x.x] += (ll)res.x.y * b[c[i]].y;
		}
		l = i + k / 2 + 1, r = k;
		if (l <= r) {
			res.clean(), get(1, l, r);
			cnt[k + b[c[i]].x + i + res.y.x] += (ll)res.y.y * b[c[i]].y;
		}
	}
	if (k % 2 == 0)
		for (int i = 1; i + k / 2 <= k; i++)
			cnt[k / 2 + b[c[i]].x + b[c[i + k / 2]].x] += (ll)b[c[i]].y * b[c[i + k / 2]].y;
	for (int i = n; i > 0; i--)
		if (cnt[i]) return cout << cnt[i], 0;
}

Compilation message

shymbulak.cpp: In function 'void build(int, int, int)':
shymbulak.cpp:100:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20480 KB Output is correct
2 Correct 11 ms 20480 KB Output is correct
3 Correct 16 ms 20480 KB Output is correct
4 Correct 12 ms 20480 KB Output is correct
5 Correct 12 ms 20480 KB Output is correct
6 Correct 11 ms 20480 KB Output is correct
7 Correct 15 ms 20480 KB Output is correct
8 Correct 12 ms 20480 KB Output is correct
9 Correct 15 ms 20480 KB Output is correct
10 Correct 13 ms 20576 KB Output is correct
11 Correct 12 ms 20480 KB Output is correct
12 Correct 12 ms 20480 KB Output is correct
13 Correct 12 ms 20480 KB Output is correct
14 Correct 12 ms 20480 KB Output is correct
15 Correct 12 ms 20608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20608 KB Output is correct
2 Correct 12 ms 20608 KB Output is correct
3 Correct 13 ms 20608 KB Output is correct
4 Correct 12 ms 20608 KB Output is correct
5 Correct 16 ms 20736 KB Output is correct
6 Correct 13 ms 20736 KB Output is correct
7 Correct 14 ms 20736 KB Output is correct
8 Correct 14 ms 20736 KB Output is correct
9 Correct 13 ms 20736 KB Output is correct
10 Correct 14 ms 20736 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 24568 KB Output is correct
2 Correct 76 ms 25088 KB Output is correct
3 Correct 66 ms 27896 KB Output is correct
4 Correct 57 ms 25208 KB Output is correct
5 Correct 63 ms 25336 KB Output is correct
6 Correct 178 ms 28316 KB Output is correct
7 Correct 117 ms 26872 KB Output is correct
8 Correct 109 ms 29816 KB Output is correct
9 Correct 109 ms 29688 KB Output is correct
10 Correct 100 ms 30584 KB Output is correct
11 Correct 115 ms 29420 KB Output is correct
12 Correct 131 ms 29928 KB Output is correct