제출 #283650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283650		rama_pang	Golf (JOI17_golf)	C++14	0 / 100	1 ms	384 KiB

golf

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

class Boundary {
 public:
  
};

void Read(int &S, int &T, int &U, int &V, int &N, 
          vector<int> &A, vector<int> &B, 
          vector<int> &C, vector<int> &D) {

  cin >> S >> T >> U >> V >> N;
  A.resize(N), B.resize(N), C.resize(N), D.resize(N);

  vector<int> xcoord = {S, U};
  vector<int> ycoord = {T, V};
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    xcoord.emplace_back(A[i]);
    xcoord.emplace_back(B[i]);
    ycoord.emplace_back(C[i]);
    ycoord.emplace_back(D[i]);
  }

  sort(begin(xcoord), end(xcoord));
  sort(begin(ycoord), end(ycoord));
  xcoord.resize(unique(begin(xcoord), end(xcoord)) - begin(xcoord));
  ycoord.resize(unique(begin(ycoord), end(ycoord)) - begin(ycoord));

  auto GetPosition = [&](const vector<int> &a, int x) {
    return lower_bound(begin(a), end(a), x) - begin(a);
  };

  S = GetPosition(xcoord, S);
  T = GetPosition(ycoord, T);
  U = GetPosition(xcoord, U);
  V = GetPosition(ycoord, V);

  for (int i = 0; i < N; i++) {
    A[i] = GetPosition(xcoord, A[i]);
    B[i] = GetPosition(xcoord, B[i]);
    C[i] = GetPosition(ycoord, C[i]);
    D[i] = GetPosition(ycoord, D[i]);
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int S, T, U, V, N;
  vector<int> A, B, C, D;
  Read(S, T, U, V, N, A, B, C, D);

  vector<array<int, 4>> walls; // (type 0 = vertical, 1 = horizontal)
  vector<array<int, 5>> lines; // (type 0 = vertical, 1 = horizontal)
  for (int i = 0; i < N; i++) {
    walls.push_back({A[i], C[i], D[i], 0});
    walls.push_back({B[i], C[i], D[i], 0});
    walls.push_back({C[i], A[i], B[i], 1});
    walls.push_back({D[i], A[i], B[i], 1});
    
    lines.push_back({A[i], C[i], D[i], 0, i * 4 + 0});
    lines.push_back({B[i], C[i], D[i], 0, i * 4 + 1});
    lines.push_back({C[i], A[i], B[i], 1, i * 4 + 2});
    lines.push_back({D[i], A[i], B[i], 1, i * 4 + 3});
  }
  lines.push_back({S, T, T, 0, N * 4 + 0});
  lines.push_back({T, S, S, 1, N * 4 + 0});
  lines.push_back({U, V, V, 0, N * 4 + 1});
  lines.push_back({V, U, U, 1, N * 4 + 1});

  vector<vector<int>> adj(4 * N + 2);
  auto AddEdge = [&](int u, int v) {
    adj[u].emplace_back(v);
  };

  for (auto &l : lines) {
    int lft = 0, rgt = 2 * N;
    for (const auto &w : walls) {
      if (l[3] != w[3] && w[1] < l[0] && l[0] < w[2]) {
        if (w[0] < l[1]) {
          lft = max(lft, w[0]);
        }
        if (l[2] < w[0]) {
          rgt = min(rgt, w[0]);
        }
      }
    }
    l[1] = lft;
    l[2] = rgt;
  }

  for (int i = 0; i < (int) lines.size(); i++) {
    for (int j = i + 1; j < (int) lines.size(); j++) if (i != j) {
      if (lines[i][3] != lines[j][3]) {
        bool c1 = lines[i][1] <= lines[j][0] && lines[j][0] <= lines[i][2];
        bool c2 = lines[j][1] <= lines[i][0] && lines[i][0] <= lines[j][2];
        if (c1 && c2) {
          AddEdge(lines[i][4], lines[j][4]);
          AddEdge(lines[j][4], lines[i][4]);
        }
      }
    }
  }

  queue<int> q;
  vector<int> dist(4 * N + 2, -1);
  q.emplace(N * 4);
  dist[N * 4] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : adj[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.emplace(v);
      }
    }
  }
  cout << dist[N * 4 + 1] << "\n";
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70