oj.uz

Submission #102717

# Submission time Handle Problem Language Result Execution time Memory
102717 2019-03-27T08:19:07 Z wxh010910 Towns (IOI15_towns) C++17
100 / 100
 33 ms 1144 KB 
#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

int hubDistance(int N, int sub) {
  vector<vector<int>> dist(2, vector<int>(N, 0));
  int root = 0, left = 0, right = 0;
  for (int i = 0; i < N; ++i) {
    if (i != root) {
      dist[0][i] = getDistance(root, i);
      if (dist[0][i] > dist[0][left]) {
        left = i;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    if (i != left) {
      dist[1][i] = getDistance(left, i);
      if (dist[1][i] > dist[1][right]) {
        right = i;
      }
    }
  }
  int limit = (dist[0][left] - dist[0][right] + dist[1][right]) >> 1;
  vector<int> from(N, 0), all;
  for (int i = 0; i < N; ++i) {
    from[i] = (dist[1][i] - dist[0][i] + dist[0][left]) >> 1;
    if (from[i] <= limit) {
      all.push_back(from[i]);
    }
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  int ans = dist[1][right];
  for (auto p : all) {
    ans = min(ans, max(p, dist[1][right] - p));
  }
  int another = root = -1;
  for (auto p : all) {
    if (max(p, dist[1][right] - p) == ans) {
      if (root == -1) {
        root = p;
      } else {
        another = p;
      }
    }
  }
  if (root != -1 && another != -1) {
    int size_left = 0;
    for (int i = 0; i < N; ++i) {
      if (from[i] <= root) {
        ++size_left;
      }
    }
    if (size_left == N - size_left) {
      return ans;
    } else if (size_left < N - size_left) {
      root = another;
    }
  }
  int last = -1, cur = 0;
  auto is_same = [&](int x, int y) {
    if (from[x] == root && from[y] == root) {
      return dist[0][x] + dist[1][y] > getDistance(x, y) + dist[0][left];
    } else {
      return (from[x] < root && from[y] < root) || (from[x] > root && from[y] > root);
    }
  };
  vector<int> type(N);
  for (int i = 0; i < N; ++i) {
    if (!cur) {
      last = i;
      ++cur;
      type[i] = 0;
    } else if (is_same(i, last)) {
      ++cur;
      type[i] = 1;
    } else {
      --cur;
      type[i] = 2;
    }
  }
  if (!cur) {
    return ans;
  }
  int best = last, total = cur = 0;
  bool same = false;
  for (int i = 0; i < N; ++i) {
    if (!type[i]) {
      if (is_same(best, i)) {
        same = true;
        ++total;
      }
      ++cur;
    } else if (type[i] == 1) {
      if (same) {
        ++total;
      }
      ++cur;
    } else {
      if (is_same(best, i)) {
        ++total;
      }
      if (!--cur) {
        same = false;
      }
    }
  }
  if (total > N >> 1) {
    return -ans;
  } else {
    return ans;
  }
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1096 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 19 ms 896 KB Output is correct
5 Correct 20 ms 896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 900 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 19 ms 896 KB Output is correct
4 Correct 22 ms 896 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 860 KB Output is correct
2 Correct 20 ms 1024 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 21 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1144 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 852 KB Output is correct
2 Correct 18 ms 896 KB Output is correct
3 Correct 18 ms 896 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 860 KB Output is correct
2 Correct 20 ms 1016 KB Output is correct
3 Correct 24 ms 896 KB Output is correct