Submission #343392

#	Time	Username	Problem	Language	Result	Execution time	Memory
343392		_ani	Shymbulak (IZhO14_shymbulak)	C++17	100 / 100	228 ms	21216 KiB

shymbulak

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int N = 200'002;
int c[N], used[N];
vector<int> g[N], h;
struct el {
	int l; ll q;
}ray[N], dp[N];
vector<el> a;
el operator+(const el& a, const el& b) {
	return { a.l,a.q + b.q };
}
bool operator<(const el& a, const el& b) {
	if (a.l == b.l)
		return a.q < b.q;
	return a.l < b.l;
}
int Dfs(int v, int p) {
	used[v] = 1;
	for(int to: g[v])
		if (to != p) {
			if (used[to]) {
				c[v] = 1;
				h.push_back(v);
				return to;
			}
			int x = Dfs(to, v);
			if (x != 0) {
				c[v] = 1;
				h.push_back(v);
				return (x == v) ? 0 : x;
			}
		}
	return 0;
}
void DfsDp(int v, int p) {
	el s;
	dp[v] = s = { -1,-1 };
	ray[v] = { 0,1 };
	for (int to : g[v])
		if (to != p && c[to] != 1) {
			DfsDp(to, v);
			//el x = Check(ray[to]);
			el x = { ray[to].l + 1, ray[to].q };
			if (x.l > ray[v].l) {
				s = ray[v];
				ray[v] = x;
			}
			else if (x.l == ray[v].l)
				ray[v].q += x.q;
			else if (x.l > s.l)
				s = x;
			else if (x.l == s.l)
				s.q += x.q;
			if (dp[v].l == dp[to].l)
				dp[v] = dp[v] + dp[to];
			if (dp[v].l < dp[to].l)
				dp[v] = dp[to];
		}
	if (s.l != -1) {
		el x = { ray[v].l + s.l, ray[v].q * s.q };
		if (x.l == dp[v].l)
			dp[v].q += x.q;
		dp[v] = max(dp[v], x);
	}
	el x;
	ll sum = 0;
	for (int to : g[v])
		if (to != p && c[to] != 1)
			if (ray[to].l + 1 == ray[v].l)
				sum += (ray[v].q - ray[to].q) * ray[to].q;
	sum /= 2;
	if (sum)x = { 2 * ray[v].l,sum };
	else x = ray[v];
	if (x.l == dp[v].l)
		dp[v].q += x.q;
	dp[v] = max(dp[v], x);
}
el t[4 * N];
void Build(int v, int vl, int vr)
{
	if (vl == vr)
	{
		t[v] = { a[vl].l,a[vl].q };
		return;
	}
	int m = (vl + vr) / 2;
	Build(v * 2, vl, m);
	Build(v * 2 + 1, m + 1, vr);
	if (t[v * 2].l == t[v * 2 + 1].l)
	{
		t[v].l = t[v * 2].l;
		t[v].q = t[v * 2].q + t[v * 2 + 1].q;
	}
	else t[v] = max(t[v * 2], t[v * 2 + 1]);
}
el GetMax(int v, int vl, int vr, int l, int r)
{
	if (vl == l && vr == r)
		return t[v];
	int m = (vl + vr) / 2;
	el r1, r2;
	if (r <= m)
		return GetMax(v * 2, vl, m, l, r);
	if (l > m)
		return GetMax(v * 2 + 1, m + 1, vr, l, r);
	r1 = GetMax(v * 2, vl, m, l, m);
	r2 = GetMax(v * 2 + 1, m + 1, vr, m + 1, r);
	if (r1.l == r2.l)
		return { r1.l,r1.q + r2.q };
	return max(r1, r2);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Dfs(1, -1);
	el ans = { 0,1 };
	for (int i = 1; i <= n; i++) {
		if (c[i]) {
			DfsDp(i, -1);
			if (dp[i].l == ans.l && ans.l != 0)
				ans.q += dp[i].q;
			else ans = max(ans, dp[i]);
		}
	//	cerr << "dp" << i << ' ' << dp[i].l << ' ' << dp[i].q << '\n';
		//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
	}
	for (int v : h)	{
	//	cerr << v << ' ';
		a.push_back(ray[v]);
	}
	//cerr << '\n';
	for (int v : h) {
		//cerr << mx1[v].l << ' ';
		a.push_back(ray[v]);
	}
	//cerr << '\n';
	//for (auto v : a)
		//cerr << v.l << ' ';
	//cerr << '\n';
	n = (int)a.size() / 2;
	for (int i = 0; i < a.size(); i++) {
		a[i].l += i;
	//	cerr << a[i].l << ' ' << a[i].q << '\n';
		//if (a[i].q == 0)a[i].q++;
	}
	//cerr << '\n';
	Build(1, 0, (int)a.size() - 1);
	//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
	for (int i = 0; i < n; i++) {
		el cur = GetMax(1, 0, 2 * n - 1, i + 1, i + n / 2);
		//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << '\n';
		cur.l -= 2 * i;
		cur.l += a[i].l;
		cur.q *= a[i].q;
		//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << "\n\n";
		if (cur.l == ans.l && ans.l != 0)
			ans.q += cur.q;
		else ans = max(ans, cur);
	}
	cout << ans.q << '\n';
	return 0;
} 

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50