oj.uz

Submission #250057

# Submission time Handle Problem Language Result Execution time Memory
250057 2020-07-16T18:33:58 Z srvlt Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 184 ms 33100 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);
	//cerr << "k " << k << '\n';
	//for (int i = 1; i <= k; i++) {
		//cerr << c[i] << ' ';
	//}
	//cerr << '\n';
	//for (int i = 1; i <= k; i++) {
		//cerr << b[c[i]].x << ' ' << b[c[i]].y;
		//if (i < k) cerr << ", ";
	//}
	//cerr << '\n';
	for (int i = 1; i <= k; i++) {
		int l = i + 1, r = min(k, i + k / 2);
		//cerr << "v " << c[i] << '\n';
		if (l <= r) {
			res.clean(), get(1, l, r);
			//cerr << "l r " << l << ' ' << r << '\n';
			//cerr << "d w " << b[c[i]].x - i + res.x.x << ' ' << (ll)res.x.y * b[c[i]].y << '\n';
			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);
			//cerr << "l r " << l << ' ' << r << '\n';
			//cerr << "d w " << k + b[c[i]].x + i + res.y.x << ' ' << (ll)res.y.y * b[c[i]].y << '\n';
			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 12 ms 20480 KB Output is correct
2 Correct 11 ms 20480 KB Output is correct
3 Correct 11 ms 20480 KB Output is correct
4 Correct 12 ms 20480 KB Output is correct
5 Correct 11 ms 20480 KB Output is correct
6 Correct 11 ms 20480 KB Output is correct
7 Correct 12 ms 20480 KB Output is correct
8 Correct 12 ms 20480 KB Output is correct
9 Correct 11 ms 20480 KB Output is correct
10 Correct 12 ms 20480 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 20480 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 24568 KB Output is correct
2 Correct 89 ms 26232 KB Output is correct
3 Correct 67 ms 29048 KB Output is correct
4 Correct 61 ms 26488 KB Output is correct
5 Correct 59 ms 26488 KB Output is correct
6 Correct 184 ms 30564 KB Output is correct
7 Correct 118 ms 28536 KB Output is correct
8 Correct 112 ms 32376 KB Output is correct
9 Correct 113 ms 32248 KB Output is correct
10 Correct 101 ms 33100 KB Output is correct
11 Correct 122 ms 31724 KB Output is correct
12 Correct 130 ms 32364 KB Output is correct