Submission #344671

#	Time	Username	Problem	Language	Result	Execution time	Memory
344671		maskoff	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	1562 ms	21868 KiB

shymbulak

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 6e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int n, mx;
vector<int> g[N], ans(N);

void go(int x) {
	vector<int> dp(n + 1, 1e9), cnt(n + 1);
	cnt[x] = 1;
	dp[x] = 0;
	queue<int> q;
	q.push(x);
	while (!q.empty()) {
	 	int v = q.front();
	 	q.pop();
	 	for (int to : g[v]) {
	 	 	if (dp[to] == dp[v] + 1) {
	 	 	 	cnt[to] += cnt[v];
	 	 	 	continue;
	 	 	}
	 	 	if (dp[to] > dp[v] + 1) {
	 	 		cnt[to] = cnt[v];
	 	 	 	dp[to] = dp[v] + 1;
	 	 	 	q.push(to);
	 	 	}
	 	}
	}
	//cerr << x << "\n";
	for (int i = 1; i <= n; i++) {
	 	//cerr << i << " " << dp[i] << " " << cnt[i] << endl;
	 	ans[dp[i]] += cnt[i];
	 	mx = max(mx, dp[i]);
	}
	cerr << endl;
}

int main() {
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n;
	for (int i = 1; i <= n; i++) {
	 	int x, y;
	 	cin >> x >> y;
	 	g[x].pb(y);
	 	g[y].pb(x);
	}
	for (int i = 1; i <= n; i++) {
	 	go(i);
	}
	cout << ans[mx] / 2;
  return 0;
}

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