Submission #1091703

# Submission time Handle Problem Language Result Execution time Memory
1091703 2024-09-21T20:25:23 Z xnqs Shymbulak (IZhO14_shymbulak) C++17
100 / 100
128 ms 39956 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
	if (gs<=5000) { // absolute fucking cinema, why does my deque not work on small graph sizes lmfaoooo
		for (int i = 0; i < ring.size(); i++) {
			for (int j = 1; j <= 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;
				}
			}
		}
	}
	else {
		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:21: 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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |    for (int j = 1; j <= ring.size()/2; j++) {
      |                    ~~^~~~~~~~~~~~~~~~
shymbulak.cpp:268:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  268 |   for (int i = 0; i < ring.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
shymbulak.cpp:274:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |   for (int i = ring.size(); i < 2*ring.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
shymbulak.cpp:275:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |    while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
      |                        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
shymbulak.cpp:279:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |    for (int j = 0; j < dq.size(); j++) {
      |                    ~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 2 ms 1372 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 1068 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 54 ms 16156 KB Output is correct
2 Correct 60 ms 17216 KB Output is correct
3 Correct 46 ms 15244 KB Output is correct
4 Correct 41 ms 14164 KB Output is correct
5 Correct 41 ms 14164 KB Output is correct
6 Correct 128 ms 33276 KB Output is correct
7 Correct 85 ms 24940 KB Output is correct
8 Correct 104 ms 27984 KB Output is correct
9 Correct 114 ms 28244 KB Output is correct
10 Correct 76 ms 28756 KB Output is correct
11 Correct 108 ms 38064 KB Output is correct
12 Correct 112 ms 39956 KB Output is correct