oj.uz

Submission #38450

# Submission time Handle Problem Language Result Execution time Memory
38450 2018-01-04T08:15:37 Z mirbek01 Hard route (IZhO17_road) C++14
19 / 100
 2000 ms 154840 KB 
# 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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 154564 KB Output is correct
2 Correct 3 ms 154564 KB Output is correct
3 Correct 3 ms 154564 KB Output is correct
4 Correct 0 ms 154564 KB Output is correct
5 Correct 3 ms 154564 KB Output is correct
6 Correct 6 ms 154564 KB Output is correct
7 Correct 6 ms 154564 KB Output is correct
8 Correct 6 ms 154564 KB Output is correct
9 Correct 6 ms 154564 KB Output is correct
10 Correct 6 ms 154564 KB Output is correct
11 Correct 26 ms 154564 KB Output is correct
12 Correct 26 ms 154564 KB Output is correct
13 Correct 26 ms 154564 KB Output is correct
14 Correct 33 ms 154564 KB Output is correct
15 Correct 3 ms 154564 KB Output is correct
16 Correct 6 ms 154564 KB Output is correct
17 Correct 3 ms 154564 KB Output is correct
18 Correct 9 ms 154564 KB Output is correct
19 Correct 0 ms 154564 KB Output is correct
20 Correct 0 ms 154564 KB Output is correct
21 Correct 3 ms 154564 KB Output is correct
22 Correct 3 ms 154564 KB Output is correct
23 Correct 3 ms 154564 KB Output is correct
24 Correct 26 ms 154564 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 154564 KB Output is correct
2 Correct 3 ms 154564 KB Output is correct
3 Correct 3 ms 154564 KB Output is correct
4 Correct 0 ms 154564 KB Output is correct
5 Correct 3 ms 154564 KB Output is correct
6 Correct 6 ms 154564 KB Output is correct
7 Correct 6 ms 154564 KB Output is correct
8 Correct 6 ms 154564 KB Output is correct
9 Correct 6 ms 154564 KB Output is correct
10 Correct 6 ms 154564 KB Output is correct
11 Correct 26 ms 154564 KB Output is correct
12 Correct 26 ms 154564 KB Output is correct
13 Correct 26 ms 154564 KB Output is correct
14 Correct 33 ms 154564 KB Output is correct
15 Correct 3 ms 154564 KB Output is correct
16 Correct 6 ms 154564 KB Output is correct
17 Correct 3 ms 154564 KB Output is correct
18 Correct 9 ms 154564 KB Output is correct
19 Correct 0 ms 154564 KB Output is correct
20 Correct 0 ms 154564 KB Output is correct
21 Correct 3 ms 154564 KB Output is correct
22 Correct 3 ms 154564 KB Output is correct
23 Correct 3 ms 154564 KB Output is correct
24 Correct 26 ms 154564 KB Output is correct
25 Execution timed out 2000 ms 154840 KB Execution timed out
26 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 154564 KB Output is correct
2 Correct 3 ms 154564 KB Output is correct
3 Correct 3 ms 154564 KB Output is correct
4 Correct 0 ms 154564 KB Output is correct
5 Correct 3 ms 154564 KB Output is correct
6 Correct 6 ms 154564 KB Output is correct
7 Correct 6 ms 154564 KB Output is correct
8 Correct 6 ms 154564 KB Output is correct
9 Correct 6 ms 154564 KB Output is correct
10 Correct 6 ms 154564 KB Output is correct
11 Correct 26 ms 154564 KB Output is correct
12 Correct 26 ms 154564 KB Output is correct
13 Correct 26 ms 154564 KB Output is correct
14 Correct 33 ms 154564 KB Output is correct
15 Correct 3 ms 154564 KB Output is correct
16 Correct 6 ms 154564 KB Output is correct
17 Correct 3 ms 154564 KB Output is correct
18 Correct 9 ms 154564 KB Output is correct
19 Correct 0 ms 154564 KB Output is correct
20 Correct 0 ms 154564 KB Output is correct
21 Correct 3 ms 154564 KB Output is correct
22 Correct 3 ms 154564 KB Output is correct
23 Correct 3 ms 154564 KB Output is correct
24 Correct 26 ms 154564 KB Output is correct
25 Execution timed out 2000 ms 154840 KB Execution timed out
26 Halted 0 ms 0 KB -