#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';
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
