Submission #1133952

#TimeUsernameProblemLanguageResultExecution timeMemory
1133952MuhammetShymbulak (IZhO14_shymbulak)C++20
50 / 100
1594 ms6524 KiB
#include "bits/stdc++.h"

using namespace std;

int n;

vector <vector <int>> v;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;
	v.resize(n+1);
	for(int i = 1; i <= n; i++){
		int u1, u2;
		cin >> u1 >> u2;
		v[u1].push_back(u2);
		v[u2].push_back(u1);
	}
	queue <int> q;
	int ans = 0, mx = 0;
	for(int i = 1; i <= n; i++){
		vector <int> dis(n+1,-1), dis1(n+1,0);
		dis[i] = 0, dis1[i] = 1;
		q.push(i);
		while(!q.empty()){
			int x = q.front();
			q.pop();
			for(auto j : v[x]){
				if(dis[j] == -1){
					dis[j] = dis[x]+1;
					dis1[j] = dis1[x];
					q.push(j);
				}
				else if(dis[j] == dis[x]+1){
					dis1[j] += dis1[x];
				}
			}
		}
		// cout << i << '\n';
		for(int j = 1; j <= n; j++){
			// cout << j << ' ' << dis[j] << "\n";
			if(dis[j] == mx) ans += dis1[j];
			else if(dis[j] > mx) ans = dis1[j], mx = dis[j];
		}
	}
	cout << ans/2 << '\n';

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...