oj.uz

답안 #343392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343392 2021-01-03T20:52:25 Z _ani 관광지 (IZhO14_shymbulak) C++17
100 / 100
 228 ms 21216 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 3 ms 5100 KB Output is correct
5 Correct 3 ms 5100 KB Output is correct
6 Correct 3 ms 5248 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 3 ms 5100 KB Output is correct
11 Correct 3 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 3 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 7 ms 5356 KB Output is correct
6 Correct 7 ms 5356 KB Output is correct
7 Correct 7 ms 5356 KB Output is correct
8 Correct 7 ms 5356 KB Output is correct
9 Correct 7 ms 5356 KB Output is correct
10 Correct 8 ms 5356 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 11392 KB Output is correct
2 Correct 128 ms 12012 KB Output is correct
3 Correct 99 ms 21216 KB Output is correct
4 Correct 80 ms 12268 KB Output is correct
5 Correct 82 ms 12140 KB Output is correct
6 Correct 228 ms 17004 KB Output is correct
7 Correct 168 ms 14888 KB Output is correct
8 Correct 163 ms 19052 KB Output is correct
9 Correct 167 ms 18540 KB Output is correct
10 Correct 159 ms 20748 KB Output is correct
11 Correct 178 ms 18528 KB Output is correct
12 Correct 188 ms 19168 KB Output is correct