제출 #1133952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133952		Muhammet	관광지 (IZhO14_shymbulak)	C++20	50 / 100	1594 ms	6524 KiB

shymbulak

#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';

}

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