oj.uz

Submission #412307

# Submission time Handle Problem Language Result Execution time Memory
412307 2021-05-26T17:04:37 Z model_code Hexagonal Territory (APIO21_hexagon) C++17
11 / 100
 1493 ms 1048580 KB 
#include "hexagon.h"
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  Point operator+(Point p) const { return Point(x+p.x, y+p.y); }
  Point operator-(Point p) const { return Point(x-p.x, y-p.y); }
  Point operator*(int s) const { return Point(x * s, y * s); }
  bool operator==(Point p) const { return x == p.x && y == p.y; }
  bool operator<(Point p) const { return x == p.x ? y < p.y : x < p.x; }
};

ostream& operator<<(ostream& os, Point p) {
  return os << "(" << p.x << ", " << p.y << ")";
}

constexpr int mod = 1e9 + 7;
const vector<Point> pdirs = { Point(0, 1), Point(1, 1), Point(1, 0),
                              Point(0, -1), Point(-1, -1), Point(-1, 0) };

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
  Point now;
  int min_x = 0, max_x = 0;
  int min_y = 0, max_y = 0;
  vector<Point> path;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < L[i]; ++j) {
      now = now + pdirs[D[i]-1];
      min_x = min(min_x, now.x);
      max_x = max(max_x, now.x);
      min_y = min(min_y, now.y);
      max_y = max(max_y, now.y);
      path.push_back(now);
    }
  }

  // Flood-fill to mark the outside of the territory
  int width = max_x - min_x + 3, height = max_y - min_y + 3;
  vector<vector<bool>> on_path(width, vector<bool>(height, false));
  Point move(-min_x + 1, -min_y + 1);
  now = now + move;
  for (auto & p : path) {
    p = p + move;
    on_path[p.x][p.y] = true;
  }
  vector<vector<int>> distance(width, vector<int>(height, -2));
  queue<Point> que;
  distance[0][0] = -1;
  que.emplace(0, 0);
  while (!que.empty()) {
    Point p = que.front();
    que.pop();
    for (auto & pdir : pdirs) {
      Point nxt = p + pdir;
      if (nxt.x < 0 || nxt.x >= width || nxt.y < 0 || nxt.y >= height)
        continue;
      if (on_path[nxt.x][nxt.y] || distance[nxt.x][nxt.y] == -1)
        continue;
      distance[nxt.x][nxt.y] = -1;
      que.push(nxt);
    }
  }

  // BFS to calculate the distances and total score.
  distance[now.x][now.y] = 0;
  long long ans = A;
  que.push(now);
  while (!que.empty()) {
    Point p = que.front();
    que.pop();
    int d = distance[p.x][p.y] + 1;
    for (auto & pdir : pdirs) {
      Point nxt = p + pdir;
      if (nxt.x < 0 || nxt.x >= width || nxt.y < 0 || nxt.y >= height)
        continue;
      if (distance[nxt.x][nxt.y] != -2)
        continue;
      distance[nxt.x][nxt.y] = d;
      ans = (ans + A + 1LL * B * d) % mod;
      que.push(nxt);
    }
  }
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1493 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1442 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 972 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 10 ms 1356 KB Output is correct
13 Correct 10 ms 1380 KB Output is correct
14 Correct 11 ms 1572 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 17 ms 2172 KB Output is correct
19 Correct 20 ms 2112 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 495 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1459 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 972 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 464 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 10 ms 1360 KB Output is correct
13 Correct 10 ms 1384 KB Output is correct
14 Correct 15 ms 1580 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Runtime error 478 ms 1048580 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1432 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1491 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -