oj.uz

Submission #387453

# Submission time Handle Problem Language Result Execution time Memory
387453 2021-04-08T12:28:03 Z rama_pang IOI Fever (JOI21_fever) C++17
6 / 100
 2 ms 492 KB 
#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) {
  map<pair<lint, lint>, int> idx;
  map<lint, set<pair<lint, lint>>> ls[5][4];
  for (int i = 0; i < N; i++) {
    idx[{X[i], Y[i]}] = i;

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

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

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

  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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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, dt + (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() {
  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

fever.cpp: In lambda function:
fever.cpp:105:3: warning: control reaches end of non-void function [-Wreturn-type]
  105 |   };
      |   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Incorrect 1 ms 364 KB Output isn't correct
30 Halted 0 ms 0 KB -