Submission #38450

#	Time	Username	Problem	Language	Result	Execution time	Memory
38450		mirbek01	Hard route (IZhO17_road)	C++14	19 / 100	2000 ms	154840 KiB

road

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 5e5 + 5;

typedef long long ll;

int n, dist[5005][5005], cnt;
ll ans;
int tin[N], tout[N], timer, p[20][N];
vector <int> g[N], v;

void dfs(int v, int par = 0){
      tin[v] = ++ timer;
      p[0][v] = par;
      for(int i = 1; i <= 17; i ++)
            p[i][v] = p[i - 1][p[i - 1][v]];
      for(int to : g[v]){
            if(to == par) continue;
            dfs(to, v);
      }
      tout[v] = timer;
}

bool upper(int a, int b){
      return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b){
      if(upper(a, b)) return a;
      if(upper(b, a)) return b;
      for(int i = 17; i >= 0; i --){
            if(!upper(p[i][a], b) && p[i][a])
                  a = p[i][a];
      }
      return p[0][a];
}

void Dfs(int i, int v, int par = 0){
      for(int to : g[v]){
            if(to == par) continue;
            dist[i][to] = dist[i][v] + 1;
            Dfs(i, to, v);
      }
}

int main(){
      scanf("%d", &n);

      for(int i = 1; i < n; i ++){
            int x, y;
            scanf("%d %d", &x, &y);
            g[x].pb(y);
            g[y].pb(x);
      }

      dfs(1, 0);

      for(int i = 1; i <= n; i ++){
            if(g[i].size() == 1) v.pb(i);
      }

      for(int i : v)
            Dfs(i, i);

      for(int ii = 0; ii < v.size(); ii ++){
            for(int jj = ii + 1; jj < v.size(); jj ++){
                  int  i = v[ii], j = v[jj];
                  int lc = lca(i, j);
                  vector <int> vec;
                  for(int k = 1; k <= n; k ++){
                        if(upper(lc, k) && (upper(k, i) || upper(k, j)))
                              vec.pb(k);
                  }
                  int H = 0;
                  for(int k = 1; k <= n; k ++){
                        int mn = inf;
                        for(int to : vec)
                              mn = min(mn, dist[k][to]);
                        H = max(H, mn);
                  }
                  ll cur = H * dist[i][j];
                  if(cur > ans){
                        ans = cur;
                        cnt = 0;
                  }
                  if(ans == cur) cnt ++;
            }
      }

      cout << ans << " " << cnt << endl;
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:75:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int ii = 0; ii < v.size(); ii ++){
                          ^
road.cpp:76:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int jj = ii + 1; jj < v.size(); jj ++){
                                     ^
road.cpp:57:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
                      ^
road.cpp:61:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &x, &y);
                                   ^

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