oj.uz

답안 #1091701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091701 2024-09-21T20:22:14 Z xnqs 관광지 (IZhO14_shymbulak) C++17
70 / 100
 123 ms 40024 KB 
// alright, so this is how this problem works (i think):
// because this graph has the special property that it only contains a simple cycle, we can view it as a "ring",
// where the simple cycle is the ring, and we root subtrees in each node of the ring.
//
// now we combine these two cases:
// 1. diameters for each subtree rooted in ring nodes, which can be done with rerooting i think;
// 2. max depth node in A's subtree with max depth node in B's subtree, where A < B and A and B are ring nodes.
//
// and i think there's a sub-quadratic way to do this..

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>

class DSU {
private:
	int n;
	std::vector<int> t;
	std::vector<int> sz;
public:
	DSU(int n): n(n) {
		t.assign(n,0); std::iota(t.begin(), t.end(), 0);
		sz.assign(n,1);
	}

	int Find(int k) {
		if (t[k]!=k) return t[k] = Find(t[k]);
		return t[k];
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);

		if (ra==rb) {
			return 0;
		}

		if (sz[ra]<sz[rb]) {
			std::swap(ra,rb);
		}

		sz[ra] += sz[rb];
		t[rb] = ra;

		return 1;
	}
};

int gs;
std::vector<std::vector<int>> graph_adj_list;
std::vector<std::vector<int>> span_adj_list;
std::vector<std::pair<int,int>> edges;
std::vector<bool> edge_in_span;
std::vector<int> ring;

// first = max, second = cnt
std::vector<std::pair<int,int64_t>> ring_subtree_diam;
std::vector<std::pair<int,int>> ring_subtree_max_depth;

std::vector<bool> in_ring;

void read_graph() {
	std::cin >> gs;

	graph_adj_list.resize(gs);
	span_adj_list.resize(gs);
	edge_in_span.assign(gs,0);
	edges.reserve(gs);
	in_ring.assign(gs,0);

	for (int i = 0, a, b; i < gs; i++) {
		std::cin >> a >> b; --a, --b;
		graph_adj_list[a].emplace_back(b);
		graph_adj_list[b].emplace_back(a);
		edges.emplace_back(a,b);
	}
}

void find_ring() {
	const auto build_spanning_tree = [&]() {
		DSU dsu(gs);
		for (int i = 0; i < gs; i++) {
			auto [a, b] = edges[i];
			if (dsu.Unite(a,b)) {
				edge_in_span[i] = 1;
				span_adj_list[a].emplace_back(b);
				span_adj_list[b].emplace_back(a);
			}
		}
	};

	const auto get_path = [&](int a, int b) {
		std::vector<int> last(gs,-2);
		std::queue<int> q;
		q.emplace(a);
		last[a] = -1;

		while (!q.empty()) {
			int k = q.front();
			q.pop();

			for (const auto& i : span_adj_list[k]) {
				if (last[i]==-2) {
					last[i] = k;
					q.emplace(i);
				}
			}
		}

		std::vector<int> ret;
		int k = b;
		while (k!=-1) {
			ret.emplace_back(k);
			k = last[k];
		}
		return ret;
	};
	
	build_spanning_tree();
	for (int i = 0; i < gs; i++) {
		if (!edge_in_span[i]) {
			auto [a, b] = edges[i];
			ring = get_path(a,b);
			for (const auto& node : ring) {
				in_ring[node] = 1;
			}
			break;
		}
	}

#ifdef DBG
	for (const auto& i : ring) {
		std::cout << i+1 << " ";
	}
	std::cout << "\n";
#endif
}

void solve_subtrees() {
	const auto solve_subtree = [&](int root) {
		ring_subtree_diam.emplace_back(-1,1);
		ring_subtree_max_depth.emplace_back(-1,1);
		std::unordered_map<int, std::pair<int,int>> dp;

		const std::function<void(int,int)> dfs = [&](int k, int p) {
			dp[k].first = 0;
			dp[k].second = 1;
			std::vector<std::pair<int,int>> max_depth_children;
			for (const auto& i : graph_adj_list[k]) {
				if (!in_ring[i]&&i!=p) {
					dfs(i,k);
					if (dp[k].first < dp[i].first + 1) {
						dp[k].first = dp[i].first + 1;
						dp[k].second = 0;
					}
					if (dp[k].first == dp[i].first + 1) {
						dp[k].second += dp[i].second;
					}
					max_depth_children.emplace_back(dp[i]);
				}
			}

			// update max depth + count
			if (k==root) {
				if (ring_subtree_max_depth.back().first < dp[k].first) {
					ring_subtree_max_depth.back().first = dp[k].first;
					ring_subtree_max_depth.back().second = 0;
				}
				if (ring_subtree_max_depth.back().first == dp[k].first) {
					ring_subtree_max_depth.back().second += dp[k].second;
				}
			}

			// update diameter + count
			std::sort(max_depth_children.begin(),max_depth_children.end(),std::greater<std::pair<int,int>>());
			if (max_depth_children.size() == 1) {
				if (ring_subtree_diam.back().first < max_depth_children[0].first + 1) {
					ring_subtree_diam.back().first = max_depth_children[0].first + 1;
					ring_subtree_diam.back().second = 0;
				}
				if (ring_subtree_diam.back().first == max_depth_children[0].first + 1) {
					ring_subtree_diam.back().second += max_depth_children[0].second;
				}
			}
			else if (max_depth_children.size() > 1) {
				int l = 0, r = 0;
				while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
					++r;
				}

				if (ring_subtree_diam.back().first < max_depth_children[0].first + max_depth_children[1].first + 2) {
					ring_subtree_diam.back().first = max_depth_children[0].first + max_depth_children[1].first + 2;
					ring_subtree_diam.back().second = 0;
				}

				if (ring_subtree_diam.back().first == max_depth_children[0].first + max_depth_children[1].first + 2) {
					if (max_depth_children[0].first == max_depth_children[1].first) {
						std::vector<int64_t> pfx(max_depth_children.size(),0);
						for (int i = 0; i <= r; i++) {
							if (i-1>=0) {
								pfx[i] += pfx[i-1];
							}
							pfx[i] += max_depth_children[i].second;
						}
						for (int i = 1; i <= r; i++) {
							ring_subtree_diam.back().second += 1LL*max_depth_children[i-1].second*(pfx[r]-pfx[i-1]);
						}
					}
					else {
						for (int i = 1; i <= r; i++) {
							ring_subtree_diam.back().second += 1LL*max_depth_children[0].second*max_depth_children[i].second;
						}
					}
				}
			}
		};

		dfs(root,-1);
	};

	for (const auto& root : ring) {
		solve_subtree(root);
	}

#ifdef DBG
	for (int i = 0; i < ring.size(); i++) {
		std::cout << ring[i]+1 << "\n";
		std::cout << ring_subtree_diam[i].first << " " << ring_subtree_diam[i].second << "\n";
		std::cout << ring_subtree_max_depth[i].first << " " << ring_subtree_max_depth[i].second << "\n";
	}
#endif

	// case 1: path is in one tree
	std::pair<int,int64_t> ans(0,0);
	for (int i = 0; i < ring.size(); i++) {
		if (ans.first < ring_subtree_diam[i].first) {
			ans.first = ring_subtree_diam[i].first;
			ans.second = 0;
		}
		if (ans.first == ring_subtree_diam[i].first) {
			ans.second += ring_subtree_diam[i].second;
		}
	}

	// case 2: tree A -> ring -> tree B
	std::deque<std::pair<int,int>> dq;
	for (int i = 0; i < ring.size(); i++) {
		while (!dq.empty()&&dq.front().first<ring_subtree_max_depth[i].first-i) {
			dq.pop_back();
		}
		dq.emplace_back(ring_subtree_max_depth[i].first-i,i);
	}
	for (int i = ring.size(); i < 2*ring.size(); i++) {
		while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
			dq.pop_front();
		}

		for (int j = 0; j < dq.size(); j++) {
			if (dq[j].first+i==dq.front().first+i) {
				if (ans.first < dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first) {
					ans.first = dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first;
					ans.second = 0;
				}
				if (ans.first == dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first) {
					ans.second += 1LL*ring_subtree_max_depth[dq[j].second%ring.size()].second*ring_subtree_max_depth[i%ring.size()].second;
				}
			}
			else {
				break;
			}
		}

		while (!dq.empty()&&dq.front().first<ring_subtree_max_depth[i%ring.size()].first-i) {
			dq.pop_back();
		}
		dq.emplace_back(ring_subtree_max_depth[i%ring.size()].first-i,i);
	}

	std::cout << ans.second << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	read_graph();
	find_ring();
	solve_subtrees();
}

Compilation message

shymbulak.cpp: In lambda function:
shymbulak.cpp:194:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:193:9: warning: unused variable 'l' [-Wunused-variable]
  193 |     int l = 0, r = 0;
      |         ^
shymbulak.cpp: In function 'void solve_subtrees()':
shymbulak.cpp:242:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |  for (int i = 0; i < ring.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shymbulak.cpp:254:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |  for (int i = 0; i < ring.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shymbulak.cpp:260:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |  for (int i = ring.size(); i < 2*ring.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~
shymbulak.cpp:261:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |   while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
      |                       ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
shymbulak.cpp:265:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |   for (int j = 0; j < dq.size(); j++) {
      |                   ~~^~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 2 ms 1368 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 17256 KB Output is correct
2 Correct 62 ms 18496 KB Output is correct
3 Correct 38 ms 15168 KB Output is correct
4 Correct 43 ms 14156 KB Output is correct
5 Correct 41 ms 14164 KB Output is correct
6 Correct 123 ms 33228 KB Output is correct
7 Correct 86 ms 25288 KB Output is correct
8 Correct 102 ms 27984 KB Output is correct
9 Correct 95 ms 28240 KB Output is correct
10 Correct 78 ms 28920 KB Output is correct
11 Correct 93 ms 38060 KB Output is correct
12 Correct 99 ms 40024 KB Output is correct