Submission #936368

#	Time	Username	Problem	Language	Result	Execution time	Memory
936368		alex_2008	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	64 ms	12132 KiB

shymbulak

#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;
}
int main() {
	int n = -1;
	cin >> n;
	if (n == -1) {
		throw "esim";
	}
	init(n);
	G.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];
	}
	vector <pair<int, int>> v;
	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, i + (m / 2));
		a.first -= i;
		v.push_back(a);
	}
	reverse(c + 1, c + m + 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, i + (m / 2));
		a.first -= i;
		v.push_back(a);
	}
	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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50