Submission #1091694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091694		xnqs	Shymbulak (IZhO14_shymbulak)	C++17	50 / 100	120 ms	17216 KiB

shymbulak

// 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++) {
		for (int j = 1; j <= std::min((size_t)727,ring.size()/2); j++) {
			if (ans.first < ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j) {
				ans.first = ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j;
				ans.second = 0;
			}
			if (ans.first == ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j) {
				ans.second += 1LL*ring_subtree_max_depth[(i-j+ring.size())%ring.size()].second*ring_subtree_max_depth[i].second;
			}
		}
	}

	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 (stderr)

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:255:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  255 |   for (int j = 1; j <= std::min((size_t)727,ring.size()/2); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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