Submission #387470

#	Time	Username	Problem	Language	Result	Execution time	Memory
387470		rama_pang	IOI Fever (JOI21_fever)	C++17	100 / 100	3219 ms	76000 KiB

fever

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint inf = 1e18;

// By case analysis, if we determine the direction
// of person 1, then all other persons have a
// unique direction in order to possibly intersect.
//
// Proof:
// Assume person 1 is at (0, 0), and goes to positive X.
// At time t, can infect at most t units away from (0, 0)
// in Manhattan distance.
//
// If there is a person at (X, Y) at quadrant 1:
// If X > Y: this person must go left, otherwise never hit
// Manhattan bounding box at any time t.
// If X < Y: this person must go down, otherwise never hit
// Manhattan bounding box at any time t.
// If X = Y: this person must go down (if person 1 goes right),
// otherwise never hit Manhattan bounding box at any time t.
//
// Case analysis is the same for all other quadrants.
//
// Fix the direction of person 1. Then, we can count all possible
// intersections by processing the persons' intersections in order.
// We can create 9N nodes: 1 for shortest time to get there, and 8
// for every possible direction. Then, we can run Dijkstra from
// person 1. Take care, that from the original shortest time node,
// we can only go to a node if the distance >= shortest_distance[u].
//
// Time complexity: O(N log N).

const vector<pair<int, int>> dxy = {
  {2, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}
};

int Solve(int N, vector<int> X, vector<int> Y, vector<int> D) {
  vector<array<lint, 5>> ls;
  vector<array<lint, 3>> idx;

  for (int i = 0; i < N; i++) {
    idx.push_back({X[i], Y[i], i});

    ls.push_back({4, 0, Y[i] + Y[i], X[i], Y[i]});
    ls.push_back({4, 1, X[i] + X[i], X[i], Y[i]});
    ls.push_back({4, 2, X[i] + Y[i], X[i], Y[i]});
    ls.push_back({4, 3, X[i] - Y[i], X[i], Y[i]});

    ls.push_back({D[i] / 2, 0, Y[i] + Y[i], X[i], Y[i]});
    ls.push_back({D[i] / 2, 1, X[i] + X[i], X[i], Y[i]});
    ls.push_back({D[i] / 2, 2, X[i] + Y[i], X[i], Y[i]});
    ls.push_back({D[i] / 2, 3, X[i] - Y[i], X[i], Y[i]});
  }

  sort(begin(ls), end(ls));
  sort(begin(idx), end(idx));

  const auto GetIndex = [&](int x, int y) {
    auto it = lower_bound(begin(idx), end(idx), array<lint, 3>({x, y, -1}));
    return (*it)[2];
  };

  const auto GetNext = [&](lint x, lint y, int dir, int ndir = 4) -> int {
    if (dir == 0) {
      const array<lint, 5> t = {ndir, 0, y + y, x, y};
      auto it = lower_bound(begin(ls), end(ls), t);
      if (it == end(ls) || (*it)[0] != t[0] || (*it)[1] != t[1] || (*it)[2] != t[2]) return -1;
      return GetIndex((*it)[3], (*it)[4]);
    }
    if (dir == 1) {
      const array<lint, 5> t = {ndir, 3, x - y, x, y};
      auto it = lower_bound(begin(ls), end(ls), t);
      if (it == end(ls) || (*it)[0] != t[0] || (*it)[1] != t[1] || (*it)[2] != t[2]) return -1;
      return GetIndex((*it)[3], (*it)[4]);
    }
    if (dir == 2) {
      const array<lint, 5> t = {ndir, 1, x + x, x, y};
      auto it = lower_bound(begin(ls), end(ls), t);
      if (it == end(ls) || (*it)[0] != t[0] || (*it)[1] != t[1] || (*it)[2] != t[2]) return -1;
      return GetIndex((*it)[3], (*it)[4]);
    }
    if (dir == 3) {
      const array<lint, 5> t = {ndir, 2, x + y, x, y};
      auto it = upper_bound(begin(ls), end(ls), t);
      if (it == begin(ls) || (*prev(it))[0] != t[0] || (*prev(it))[1] != t[1] || (*prev(it))[2] != t[2]) return -1;
      return GetIndex((*prev(it))[3], (*prev(it))[4]);
    }
    if (dir == 4) {
      const array<lint, 5> t = {ndir, 0, y + y, x, y};
      auto it = upper_bound(begin(ls), end(ls), t);
      if (it == begin(ls) || (*prev(it))[0] != t[0] || (*prev(it))[1] != t[1] || (*prev(it))[2] != t[2]) return -1;
      return GetIndex((*prev(it))[3], (*prev(it))[4]);
    }
    if (dir == 5) {
      const array<lint, 5> t = {ndir, 3, x - y, x, y};
      auto it = upper_bound(begin(ls), end(ls), t);
      if (it == begin(ls) || (*prev(it))[0] != t[0] || (*prev(it))[1] != t[1] || (*prev(it))[2] != t[2]) return -1;
      return GetIndex((*prev(it))[3], (*prev(it))[4]);
    }
    if (dir == 6) {
      const array<lint, 5> t = {ndir, 1, x + x, x, y};
      auto it = upper_bound(begin(ls), end(ls), t);
      if (it == begin(ls) || (*prev(it))[0] != t[0] || (*prev(it))[1] != t[1] || (*prev(it))[2] != t[2]) return -1;
      return GetIndex((*prev(it))[3], (*prev(it))[4]);
    }
    if (dir == 7) {
      const array<lint, 5> t = {ndir, 2, x + y, x, y};
      auto it = lower_bound(begin(ls), end(ls), t);
      if (it == end(ls) || (*it)[0] != t[0] || (*it)[1] != t[1] || (*it)[2] != t[2]) return -1;
      return GetIndex((*it)[3], (*it)[4]);
    }
  };

  vector<lint> dist(9 * N, inf);
  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;

  const auto Relax = [&](int u, int dir, lint d) {
    if (dist[N * dir + u] > d) {
      dist[N * dir + u] = d;
      pq.emplace(dist[N * dir + u], N * dir + u);
    }
  };

  Relax(0, 8, 0);
  while (!pq.empty()) {
    int u = pq.top().second % N;
    int di = pq.top().second / N;
    lint dt = pq.top().first;
    pq.pop();
    if (dist[N * di + u] != dt) {
      continue;
    }
    Relax(u, 8, dt);
    if (di == 8) {
      if (D[u] == 0) {
        if (int dir = 7, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 1); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 0, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 2); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 1, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 3); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
      }
      if (D[u] == 2) {
        if (int dir = 1, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 2); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 2, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 3); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 3, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 0); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
      }
      if (D[u] == 4) {
        if (int dir = 3, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 3); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 4, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 0); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 5, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 1); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
      }
      if (D[u] == 6) {
        if (int dir = 5, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 0); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 6, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 1); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
        if (int dir = 7, v = GetNext(X[u] + dxy[dir].first * dt, Y[u] + dxy[dir].second * dt, dir, 2); v != -1) {
          Relax(v, dir, (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
        }
      }
    } else {
      if (int dir = di, v = GetNext(X[u] + dxy[dir].first, Y[u] + dxy[dir].second, dir); v != -1) {
        Relax(v, dir, dt + (abs(X[u] - X[v]) + abs(Y[u] - Y[v])) / 2);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += dist[N * 8 + i] != inf;
  }
  return ans;
}

vector<int> Direction(int N, vector<int> X, vector<int> Y) {
  vector<int> D(N);
  D[0] = 0;
  for (int i = 1; i < N; i++) {
    if (abs(X[i]) == abs(Y[i])) {
      if (X[i] > 0 && Y[i] > 0) {
        D[i] = 6;
      } else if (X[i] > 0 && Y[i] < 0) {
        D[i] = 2;
      } else {
        D[i] = 0;
      }
    } else {
      if (X[i] >= 0 && Y[i] >= 0) {
        if (abs(X[i]) > abs(Y[i])) {
          D[i] = 4;
        } else {
          D[i] = 6;
        }
      } else if (X[i] <= 0 && Y[i] >= 0) {
        if (abs(X[i]) > abs(Y[i])) {
          D[i] = 0;
        } else {
          D[i] = 6;
        }
      } else if (X[i] <= 0 && Y[i] <= 0) {
        if (abs(X[i]) > abs(Y[i])) {
          D[i] = 0;
        } else {
          D[i] = 2;
        }
      } else if (X[i] >= 0 && Y[i] <= 0) {
        if (abs(X[i]) > abs(Y[i])) {
          D[i] = 4;
        } else {
          D[i] = 2;
        }
      }
    }
  }

  return D;
}

int main() {
  auto start = clock();

  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;

  vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    X[i] *= 2; Y[i] *= 2;
  }

  for (int i = N - 1; i >= 0; i--) { // Initial person at (0, 0)
    X[i] -= X[0];
    Y[i] -= Y[0];
  }

  int ans = 0;
  for (int d = 0; d < 4; d++) {
    ans = max(ans, Solve(N, X, Y, Direction(N, X, Y)));
    for (int i = 0; i < N; i++) {
      tie(X[i], Y[i]) = pair(-Y[i], X[i]);
    }
  }

  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:240:8: warning: unused variable 'start' [-Wunused-variable]
  240 |   auto start = clock();
      |        ^~~~~
fever.cpp: In lambda function:
fever.cpp:114:3: warning: control reaches end of non-void function [-Wreturn-type]
  114 |   };
      |   ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31