oj.uz

Submission #899363

# Submission time Handle Problem Language Result Execution time Memory
899363 2024-01-05T21:32:29 Z MilosMilutinovic Hard route (IZhO17_road) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  vector<int> mx(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    mx[v] = 1;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      mx[v] = max(mx[v], mx[u] + 1);
    }
  };
  long long res = 0;
  long long cnt = 1;
  for (int i = 0; i < n; i++) {
    Dfs(i, i);
    vector<int> f;
    for (int j : g[i]) {
      f.push_back(mx[j]);
    }
    sort(f.rbegin(), f.rend());
    if ((int) f.size() <= 2) {
      continue;
    }
    long long new_res = f[0] * (f[1] + f[2]);
    if (new_res < res) {
      continue;
    }
    vector<int> c(3);
    for (int x : f) {
      for (int k = 0; k < 3; k++) {
        if (f[k] == x) {
          c[k] += 1;
        }
      }
    }
    long long new_cnt = 0;
    if (f[0] == f[2]) {
      new_cnt = c[0] * 1LL * (c[0] - 1) * 1LL * (c[0] - 2) / 2;
    } else if (f[0] == f[1]) {
      new_cnt = c[0] * 1LL * (c[0] - 1) * 1LL * c[2];
    } else if (f[1] == f[2]) {
      new_cnt = c[0] * 1LL * c[1] * 1LL * (c[1] - 1) / 2;
    } else {
      new_cnt = c[0] * 1LL * c[1] * 1LL * c[2];
    }
    if (new_res == res) {
      cnt += new_cnt;
    } else {
      assert(new_res > res);
      res = new_res;
      cnt = new_cnt;
    }
  }
  cout << res << " " << cnt << '\n';
  return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -