oj.uz

답안 #1091682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091682 2024-09-21T19:40:53 Z xnqs 관광지 (IZhO14_shymbulak) C++17
50 / 100
 1500 ms 17216 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>

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) {
						// TODO pfx sums but cba rn ez
						for (int i = l; i <= r; i++) {
							for (int j = i+1; j <= r; j++) {
								ring_subtree_diam.back().second += 1LL*max_depth_children[i].second*max_depth_children[j].second;
							}
						}
					}
					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

	// now all we have to do is implement this little fucker here efficiently
	// cht/lichao/linecontainer?
	std::pair<int,int64_t> ans(0,0);
	for (int i = 0; i < ring.size(); i++) {
		// case 1: path is in one tree
		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: path crosses from one tree to the other
		for (int j = 1; j <= ring.size()/2; j++) {
			//std::cout << ring[i]+1 << " " << ring[(i+j)%ring.size()]+1 << " " << j + ring_subtree_max_depth[i].first + ring_subtree_max_depth[(i+j)%ring.size()].first << " " << 1LL*ring_subtree_max_depth[i].second*ring_subtree_max_depth[(i+j)%ring.size()].second << "\n";
			if (ans.first < ring_subtree_max_depth[i].first + ring_subtree_max_depth[(i+j)%ring.size()].first + j) {
				ans.first = ring_subtree_max_depth[i].first + ring_subtree_max_depth[(i+j)%ring.size()].first + j;
				ans.second = 0;
			}
			if (ans.first == ring_subtree_max_depth[i].first + ring_subtree_max_depth[(i+j)%ring.size()].first + j) {
				ans.second += 1LL*ring_subtree_max_depth[i].second*ring_subtree_max_depth[(i+j)%ring.size()].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

shymbulak.cpp: In lambda function:
shymbulak.cpp:193: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]
  193 |     while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'void solve_subtrees()':
shymbulak.cpp:238:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |  for (int i = 0; i < ring.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shymbulak.cpp:249:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |   for (int j = 1; j <= ring.size()/2; j++) {
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
30.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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 11 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 3 ms 984 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 16236 KB Output is correct
2 Correct 58 ms 17216 KB Output is correct
3 Execution timed out 1535 ms 15168 KB Time limit exceeded
4 Halted 0 ms 0 KB -