Submission #1102877

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102877	2024-10-19T06:44:19 Z	Muhammet	Hard route (IZhO17_road)	C++17	19 / 100	2000 ms	98896 KB

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.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	376 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	428 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	3 ms	496 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct

Subtask #2

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	376 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	428 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	3 ms	496 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Execution timed out	2057 ms	98896 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #3

0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	376 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	428 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	3 ms	496 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Execution timed out	2057 ms	98896 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-