Submission #1102877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102877		Muhammet	Hard route (IZhO17_road)	C++17	19 / 100	2057 ms	98896 KiB

road

#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

int n;

vector <vector <int>> v, dis;

vector <int> v1;

void dfs(int x, int y){
	v1.push_back(y);
	for(auto i : v[y]){
		if(dis[x][i] == dis[x][y] - 1){
			dfs(x,i);
			return;
		}
	}
}

int main(){
	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);
	}
	dis.assign(n+1, vector <int> (n+1,1e9));
	for(int i = 1; i <= n; i++){
		queue <int> q;
		q.push(i);
		dis[i][i] = 0;
		while(!q.empty()){
			int x = q.front();
			q.pop();
			for(auto j : v[x]){
				if(dis[i][j] > dis[i][x] + 1){
					dis[i][j] = dis[i][x] + 1;
					q.push(j);
				}
			}
		}
		// for(int j = 1; j <= n; j++){
		// 	cout << dis[i][j] << ' ';
		// }
		// cout << '\n';
	}
	int mx = 0, nm = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(sz(v[i]) == 1 and sz(v[j]) == 1){
				v1.clear();
				dfs(i,j);
				sort(v1.begin(), v1.end());
				int ind = 0, mmx = 0;
				for(int k = 1; k <= n; k++){
					if(k == v1[ind]){
						ind++;
						continue;
					}
					int mn = 1e9;
					for(auto k1 : v1){
						mn = min(mn, dis[k][k1]);
					}
					mmx = max(mmx,mn);
				}
				// cout << mmx << '\n';
				if(mmx*(sz(v1)-1) > mx){
					nm = 1;
					mx = (mmx * (sz(v1)-1));
				}
				else if(mx == (mmx * (sz(v1)-1))){
					nm++;
				}
			}
		}
	}
	cout << mx << ' ' << nm << '\n';
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48