Submission #1275992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275992		julia_08	Hard route (IZhO17_road)	C++20	52 / 100	276 ms	1100 KiB

road

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 5e3 + 10;

int dist[MAXN], dp[MAXN];

vector<int> adj[MAXN];

pair<int, int> ans;

void dfs_1(int v, int p){

  dp[v] = 0;

  for(auto u : adj[v]){
    if(u != p){

      dist[u] = dist[v] + 1;
      dfs_1(u, v);

      dp[v] = max(dp[v], dp[u] + 1);

    }
  }

}

void dfs_2(int v, int p, int max_dist){

  if(adj[v].size() == 1 && v != p){

    if(dist[v] * max_dist > ans.first){
      ans = {dist[v] * max_dist, 1};
    } else if(dist[v] * max_dist == ans.first) ans.second ++;

  }

  pair<int, int> max_prof = {0, 0};

  for(auto u : adj[v]){
    if(u != p){
      if(dp[u] + 1 >= max_prof.first){
        max_prof = {dp[u] + 1, max_prof.first};
      } else max_prof.second = max(max_prof.second, dp[u] + 1);
    }
  }

  for(auto u : adj[v]){
    if(u != p){

      int cur_dist = max_prof.first;

      if(dp[u] + 1 == max_prof.first) cur_dist = max_prof.second;

      dfs_2(u, v, max(max_dist, cur_dist));

    }
  }

}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  for(int i=1; i<n; i++){
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  for(int i=1; i<=n; i++){
    if(adj[i].size() == 1){

      dist[i] = 0;

      dfs_1(i, i);
      dfs_2(i, i, 0);

    }
  }

  cout << ans.first << " " << ans.second / 2 << "\n";

  return 0;
}

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