oj.uz

답안 #1111870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111870 2024-11-13T08:48:43 Z vjudge1 관광지 (IZhO14_shymbulak) C++17
100 / 100
 130 ms 40528 KB 
#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:184: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]
  184 |     while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:183:9: warning: unused variable 'l' [-Wunused-variable]
  183 |     int l = 0, r = 0;
      |         ^
shymbulak.cpp: In function 'void solve_subtrees()':
shymbulak.cpp:232:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |  for (int i = 0; i < ring.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shymbulak.cpp:244:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |   for (int i = 0; i < ring.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
shymbulak.cpp:245:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |    for (int j = 1; j <= ring.size()/2; j++) {
      |                    ~~^~~~~~~~~~~~~~~~
shymbulak.cpp:258:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |   for (int i = 0; i < ring.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
shymbulak.cpp:264:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |   for (int i = ring.size(); i < 2*ring.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
shymbulak.cpp:265:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |    while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
      |                        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
shymbulak.cpp:269: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]
  269 |    for (int j = 0; j < dq.size(); j++) {
      |                    ~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 3 ms 984 KB Output is correct
6 Correct 4 ms 1360 KB Output is correct
7 Correct 4 ms 1104 KB Output is correct
8 Correct 4 ms 1104 KB Output is correct
9 Correct 3 ms 1104 KB Output is correct
10 Correct 3 ms 1272 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 17248 KB Output is correct
2 Correct 59 ms 18488 KB Output is correct
3 Correct 39 ms 15224 KB Output is correct
4 Correct 48 ms 14152 KB Output is correct
5 Correct 43 ms 14160 KB Output is correct
6 Correct 130 ms 33224 KB Output is correct
7 Correct 108 ms 24928 KB Output is correct
8 Correct 95 ms 27980 KB Output is correct
9 Correct 97 ms 28232 KB Output is correct
10 Correct 81 ms 28844 KB Output is correct
11 Correct 114 ms 38820 KB Output is correct
12 Correct 119 ms 40528 KB Output is correct