#include <bits/stdc++.h>
#include <array>
#define setall(a, val) for(auto& x : a) x = val
#define all(v) (v.begin()), (v.end())
#define cerr (cerr << "D: ")
#define ll long long
using namespace std;
clock_t start_time;
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
void init(bool oj = 0) {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
srand(time(0)); start_time = clock();
if (!oj) {
#ifndef ONLINE_JUDGE
FILE* _ = freopen("in.txt", "r", stdin);
//FILE* __ = freopen("out.txt", "w", stdout);
#endif
}
}
const ll HASH_BASE = 31;
const ll MOD = 2000000011;
const ll N = 5e3 + 7;
const ll M = 1e7 + 1e7 / 2;
//####################################################################################
int d[N][N], mx[N], t;
vector<int> path;
vector < vector<int> > v;
void dfs(int x, int p) {
path.push_back(x);
if (x == t || t == -1) {
t = -1;
return;
}
for (int n : v[x]) {
if (n != p)
dfs(n, x);
if (t == -1)
return;
}
path.pop_back();
}
int main() {
init();
int n;
cin >> n;
v.resize(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> l;
for (int i = 0; i < n; i++) {
if (v[i].size() == 1)
l.push_back(i);
queue<array<int, 2>>q;
q.push({ i, 0 });
while (q.size()) {
array<int, 2> a = q.front();
q.pop();
if (d[i][a[0]])
continue;
d[i][a[0]] = a[1];
mx[i] = max(mx[i], d[i][a[0]]);
for (int x : v[a[0]]) {
if (x != i)
q.push({ x, a[1] + 1 });
}
}
}
ll ans = 0;
for (int i = 0; i < l.size(); i++) {
for (int j = 0; j < l.size(); j++) {
t = l[j];
path.clear();
dfs(l[i], l[i]);
ll m = 0;
for (int x : path)
m = max((ll)mx[x], m);
ans = max(ans, m * d[l[i]][l[j]]);
}
}
cout << ans << endl;
cerr << get_time() << "s" << endl;
}
Compilation message
road.cpp: In function 'void init(bool)':
road.cpp:15:9: warning: unused variable '_' [-Wunused-variable]
15 | FILE* _ = freopen("in.txt", "r", stdin);
| ^
road.cpp: In function 'int main()':
road.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < l.size(); i++) {
| ~~^~~~~~~~~~
road.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int j = 0; j < l.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
