Submission #1169639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169639		shiomusubi496	Golf (JOI17_golf)	C++20	30 / 100	568 ms	318952 KiB

golf

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;
using PLL = pair<ll, ll>;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

constexpr ll inf = 1e18;

constexpr int dx[] = {0, 1, 0, -1};
constexpr int dy[] = {1, 0, -1, 0};

int main() {
    int sx, sy, tx, ty; scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
    int N; scanf("%d", &N);
    vector<array<int, 4>> A(N);
    rep (i, N) rep (j, 4) scanf("%d", &A[i][j]);
    vector<int> Xs{sx, tx}, Ys{sy, ty};
    rep (i, N) {
        Xs.push_back(A[i][0]);
        Xs.push_back(A[i][1]);
        Ys.push_back(A[i][2]);
        Ys.push_back(A[i][3]);
    }
    sort(all(Xs)); Xs.erase(unique(all(Xs)), Xs.end());
    sort(all(Ys)); Ys.erase(unique(all(Ys)), Ys.end());
    sx = lower_bound(all(Xs), sx) - Xs.begin();
    tx = lower_bound(all(Xs), tx) - Xs.begin();
    sy = lower_bound(all(Ys), sy) - Ys.begin();
    ty = lower_bound(all(Ys), ty) - Ys.begin();
    rep (i, N) {
        A[i][0] = lower_bound(all(Xs), A[i][0]) - Xs.begin();
        A[i][1] = lower_bound(all(Xs), A[i][1]) - Xs.begin();
        A[i][2] = lower_bound(all(Ys), A[i][2]) - Ys.begin();
        A[i][3] = lower_bound(all(Ys), A[i][3]) - Ys.begin();
    }
    int H = Xs.size(), W = Ys.size();
    assert((ll)H * W <= 10000000);
    vector<vector<int>> cum(H, vector<int>(W));
    rep (i, N) {
        ++cum[A[i][0]][A[i][2]];
        --cum[A[i][0]][A[i][3]];
        --cum[A[i][1]][A[i][2]];
        ++cum[A[i][1]][A[i][3]];
    }
    rep (i, H) rep (j, W - 1) cum[i][j + 1] += cum[i][j];
    rep (i, H - 1) rep (j, W) cum[i + 1][j] += cum[i][j];
    vector dist(H, vector(W, vector(4, inf)));
    deque<tuple<int, int, int, int>> que;
    rep (i, 4) {
        dist[sx][sy][i] = 1;
        que.emplace_back(sx, sy, i, 1);
    }
    while (!que.empty()) {
        auto [x, y, d, c] = que.front(); que.pop_front();
        if (dist[x][y][d] != c) continue;
        rep (i, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (i % 2 == 0) {
                if (x != 0 && cum[x - 1][min(y, ny)] != 0 && cum[x][min(y, ny)] != 0) continue;
            }
            else {
                if (y != 0 && cum[min(x, nx)][y - 1] != 0 && cum[min(x, nx)][y] != 0) continue;
            }
            int nc = c + (d != i);
            if (chmin(dist[nx][ny][i], nc)) {
                if (d == i) que.emplace_front(nx, ny, i, nc);
                else que.emplace_back(nx, ny, i, nc);
            }
        }
    }
    ll ans = inf;
    rep (i, 4) chmin(ans, dist[tx][ty][i]);
    printf("%lld\n", ans);
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:24:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     int sx, sy, tx, ty; scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     int N; scanf("%d", &N);
      |            ~~~~~^~~~~~~~~~
golf.cpp:27:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     rep (i, N) rep (j, 4) scanf("%d", &A[i][j]);
      |                           ~~~~~^~~~~~~~~~~~~~~~

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