oj.uz

답안 #936413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936413 2024-03-01T18:56:04 Z alex_2008 관광지 (IZhO14_shymbulak) C++14
100 / 100
 171 ms 36168 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].second * 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";
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8652 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 4 ms 9308 KB Output is correct
7 Correct 5 ms 9100 KB Output is correct
8 Correct 5 ms 9052 KB Output is correct
9 Correct 4 ms 9052 KB Output is correct
10 Correct 6 ms 9052 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 17868 KB Output is correct
2 Correct 79 ms 18124 KB Output is correct
3 Correct 73 ms 36168 KB Output is correct
4 Correct 68 ms 18072 KB Output is correct
5 Correct 83 ms 18260 KB Output is correct
6 Correct 171 ms 26312 KB Output is correct
7 Correct 133 ms 22192 KB Output is correct
8 Correct 145 ms 27836 KB Output is correct
9 Correct 149 ms 28004 KB Output is correct
10 Correct 134 ms 29520 KB Output is correct
11 Correct 115 ms 31300 KB Output is correct
12 Correct 121 ms 35676 KB Output is correct