Submission #486651

#	Time	Username	Problem	Language	Result	Execution time	Memory
486651		ez_ioi	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	39 ms	12804 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 5e3 + 1, mod = 1e9 + 7, LOG = 20;

int n, b, a, cl[mxN], p[mxN], dist[mxN][mxN], root[mxN];
bool ok[mxN][mxN];
bool used[mxN], was[mxN];
vector <int> adj[mxN], cur, c;
bool found;

bool dfs(int v, int par = -1) {
	used[v] = 1;
	cur.push_back(v);
	for (auto to : adj[v]) {
		if (to == par) continue;
		if (used[to]) {
			if (!found) c = cur;
			found = 1;
			return 1;
		}
		else {
			if (dfs(to, v)) return 1;
		}
	}
	cur.pop_back();
	used[v] = 0;
	return 0;
}

void dfs2(int v, int rt, int par = -1) {
	root[v] = rt;
	for (auto to : adj[v]) {
		if (!used[to] && to != par) 
			dfs2(to, rt, v);
	}
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1, u, v; i <= n; ++i) {
		cin >> u >> v;
		adj[u].push_back(v); adj[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) {
		if (dfs(i)) break;
	}
	for (int i = 1; i <= n; ++i) used[i] = 0;
	int len = c.size() - 1;
	for (int i = 0; i < c.size(); ++i) {
		used[c[i]] = 1;
		for (int j = 1; j <= len; ++j) {
			int x = c[(i - j + (int)c.size()) % (int)c.size()];
			int y = c[(i + j) % (int)c.size()];
			if (x == y) {
				ok[c[i]][y] = 1;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		queue <int> q;
		q.push(i); was[i] = 1;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto to : adj[v]) {
				if (!was[to]) {
					was[to] = 1;
					dist[i][to] = dist[i][v] + 1;
					q.push(to);
				}
			}
		}
		for (int j = 1; j <= n; ++j) was[j] = 0;
	}	
	for (int i = 1; i <= n; ++i) {
		if (used[i]) dfs2(i, i);
	}
	int bruh = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) bruh = max(bruh, dist[i][j]);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (dist[i][j] == bruh) {
				++ans;
				ans += ok[root[i]][root[j]];			
			}
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0; i < c.size(); ++i) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50