Submission #337903

#	Time	Username	Problem	Language	Result	Execution time	Memory
337903		boykut	Hard route (IZhO17_road)	C++14	19 / 100	2089 ms	196972 KiB

road

#include <bits/stdc++.h>

using namespace std;

int N;

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n;
   cin >> n;
   N = n;
   vector <int> g[n + 1];
   for (int i = 0; i < n - 1; i++) {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
      g[b].push_back(a);
   }
   vector <int> d[1+N], p[1+N];
   for (int i = 1; i <= n; i++) {
      queue <int> q;
      q.push(i);
      d[i] = vector <int> (1+N, INT_MAX);
      p[i] = vector <int> (1+N, -1);
      d[i][i] = 0;
      while (!q.empty()) {
         int v = q.front();
         q.pop();
         for (int to : g[v]) {
            if (d[i][to] != INT_MAX) continue;
               d[i][to] = d[i][v] + 1;
               p[i][to] = v;
               q.push(to);
         }
      }
   }
   vector <int> ends;
   for (int i = 1; i <= n; i++) {
      if (g[i].size() == 1) {
         ends.push_back(i);
      }
   }
   int ans = 0, ans_cnt = 0;
   for (int i = 0; i < ends.size(); i++) {
      int a = ends[i];
      for (int j = i + 1; j < ends.size(); j++) {
         int b = ends[j];
         if (d[b][a] == INT_MAX) continue;
         int v = a;
         //vector <int> mas;
         set <int> st;
         while (v != -1) {
         //   mas.push_back(v);
            st.insert(v);
            v = p[b][v];
         }
         //for (int i = 0; i < mas.size(); i++) {
         //   cout << mas[i] << (i == mas.size()-1?" ":"-");
         //}
         //cout << "= " << d[b][a] << ' ';
         int mx = 0;
         for (int from = 1; from <= n; from++) {
            if (st.count(from)) continue;
            int mn = INT_MAX;
            for (int to : st) {
               mn = min(mn, d[from][to]);
            }
            mx = max(mx, mn);
         }
         if (mx * d[b][a] == ans) {
            ans_cnt++;
         } else if (mx * d[b][a] > ans) {
            ans = mx * d[b][a];
            ans_cnt = 1;
         }
      }
   }
   cout << ans << ' ' << ans_cnt << '\n';
   return 0;
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int i = 0; i < ends.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
road.cpp:47:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       for (int j = i + 1; j < ends.size(); j++) {
      |                           ~~^~~~~~~~~~~~~

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