답안 #936411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936411 2024-03-01T18:55:00 Z alex_2008 관광지 (IZhO14_shymbulak) C++14
0 / 100
162 ms 37444 KB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
int par[N], rankk[N];
int p[N];
bool used[N], in_cycle[N];
pair<int, int> c[2 * N];
pair<int, int> st[2 * N][20];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		rankk[i] = 0;
	}
}
int find_set(int v) {
	if (par[v] == v) return v;
	return par[v] = find_set(par[v]);
}
bool union_sets(int a, int b) {
	a = find_set(a);
	b = find_set(b);
	if (a == b) return false;
	if (rankk[a] > rankk[b]) swap(a, b);
	par[a] = b;
	if (rankk[a] == rankk[b]) rankk[b]++;
	return true;
}
vector <vector<int>> G;
pair<int, int> dfs(int v, int p) {
	pair <int, int> ret = make_pair(0, 1);
	for (auto it : G[v]) {
		if (in_cycle[it]) continue;
		if (it == p) continue;
		pair <int, int> a = dfs(it, v);
		a.first++;
		if (a.first > ret.first) {
			ret = a;
		}
		else if (a.first == ret.first) {
			ret.second += a.second;
		}
	}
	return ret;
}
pair <int, int> mx_in_range(int l, int r) {
	pair <int, int> ret = make_pair(0, 0);
	for (int i = 19; i >= 0; i--) {
		if ((r - l + 1) >= (1 << i)) {
			pair <int, int> a = st[l][i];
			if (a.first > ret.first) ret = a;
			else if (a.first == ret.first) ret.second += a.second;
			l += (1 << i);
		}
	}
	return ret;
}
pair<int, int> mx[N];
vector <vector<int>> child;
int w;
vector <int> vert;
vector <pair<int, long long>> v;
void dfss(int v, int p) {
	vert.push_back(v);
	mx[v] = make_pair(0, 1);
	for (auto it : G[v]) {
		if (it == p) continue;
		if (in_cycle[it]) continue;
		dfss(it, v);
		if (mx[it].first + 1 > mx[v].first) {
			mx[v] = make_pair(mx[it].first + 1, mx[it].second);
		}
		else if (mx[it].first + 1 == mx[v].first) {
			mx[v] = make_pair(mx[v].first, mx[v].second + mx[it].second);
		}
		child[v].push_back(it);
	}
}
pair <int, long long> f(int v) {
	vert.clear();
	pair <int, long long> ret = make_pair(0, 1);
	dfss(v, -1);
	for (auto it : vert) {
		if (mx[it].first > ret.first) {
			ret = mx[it];
		}
		else if (mx[it].first == ret.first) {
			ret.second += mx[it].second;
		}
		vector <pair<int, long long>> cur;
		for (auto j : child[it]) {
			cur.push_back(mx[j]);
		}
		sort(cur.begin(), cur.end());
		reverse(cur.begin(), cur.end());
		if (cur.size() <=  1) continue;
		if (cur[0].first == cur[1].first) {
			int last = 1;
			for (int i = 2; i < (int)cur.size(); i++) {
				if (cur[i].first == cur[0].first) last = i;
			}
			long long v = 0;
			for (int i = 0; i <= last; i++) {
				v += cur[i].second;
			}
			pair <int, long long> qwe;
			qwe.first = 2 * cur[0].first + 2;
			for (int i = 0; i < last; i++) {
				v -= cur[i].second;
				qwe.second += (cur[i].first * 1ll * v);
			}
			if (qwe.first > ret.first) ret = qwe;
			else if (qwe.first == ret.first) ret.second += qwe.second;
			continue;
		}
		long long v = 0;
		for (int i = 1; i < (int)cur.size(); i++) {
			if (cur[i].first == cur[1].first) v += cur[i].second;
		}
		pair <int, long long> qwe;
		qwe.first = cur[0].first + cur[1].first + 2;
		qwe.second = (cur[0].second * 1ll * v);
		if (qwe.first > ret.first) ret = qwe;
		else if (qwe.first == ret.first) ret.second += qwe.second;
	}
	return ret;
}
int main() {
	int n = -1;
	cin >> n;
	//if (n == -1) {
	//	throw "esim";
	//}
	init(n);
	G.resize(n + 1);
	child.resize(n + 1);
	int a = -1, b = -1;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		if (union_sets(x, y)) {
			G[x].push_back(y);
			G[y].push_back(x);
			continue;
		}
		a = x; b = y;
	}
	//cout << "!" << a << " " << b << "\n";
	for (int i = 1; i <= n; i++) {
		used[i] = false;
	}
	vector <int> cycle;
	queue <int> q;
	q.push(a);
	used[a] = true;
	while (!q.empty()) {
		int v = q.front(); q.pop();
		for (auto it : G[v]) {
			if (!used[it]) {
				p[it] = v;
				used[it] = true;
				q.push(it);
			}
		}
	}
	cycle.push_back(b);
	while (cycle.back() != a) {
		cycle.push_back(p[cycle.back()]);
	}
	//for (auto it : cycle) {
	//	cout << it << " ";
	//}
	//cout << "\n";
	for (auto it : cycle) {
		in_cycle[it] = true;
	}
	int m = (int)cycle.size();
	//if (m < 3) {
	//	throw "esim";
	//}
	for (int i = 1; i <= m; i++) {
		c[i] = dfs(cycle[i - 1], -1);
	}
	for (int i = m + 1; i <= 2 * m; i++) {
		c[i] = c[i - m];
	}
	for (int i = 2 * m; i >= 1; i--) {
		st[i][0] = make_pair(c[i].first + i, c[i].second);
		for (int j = 1; j < 20; j++) {
			if ((i + (1 << j) - 1) > 2 * m) break;
			pair <int, int> a = st[i][j - 1];
			pair <int, int> b = st[i + (1 << (j - 1))][j - 1];
			if (a.first < b.first) swap(a, b);
			if (a.first == b.first) st[i][j] = make_pair(a.first, a.second + b.second);
			else st[i][j] = a;
		}
	}
	for (int i = 1; i <= m; i++) {
		pair <int, int> a = mx_in_range(i + 1, i + (m / 2));
		a.first -= i;
		a.first += c[i].first;
		v.push_back(make_pair(a.first, c[i].second * 1ll * a.second));
	}
	for (auto it : cycle) {
		v.push_back(f(it));
	}
	sort(v.begin(), v.end());
	long long ans = 0;
	for (auto it : v) {
		if (it.first == v.back().first) ans += it.second;
	}
	cout << ans << "\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8644 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 18836 KB Output is correct
2 Correct 72 ms 19192 KB Output is correct
3 Correct 73 ms 37444 KB Output is correct
4 Correct 66 ms 19280 KB Output is correct
5 Correct 67 ms 19352 KB Output is correct
6 Correct 162 ms 28552 KB Output is correct
7 Correct 110 ms 23884 KB Output is correct
8 Correct 146 ms 30296 KB Output is correct
9 Correct 148 ms 30408 KB Output is correct
10 Correct 138 ms 32024 KB Output is correct
11 Incorrect 114 ms 34884 KB Output isn't correct
12 Halted 0 ms 0 KB -