Submission #129520

#	Time	Username	Problem	Language	Result	Execution time	Memory
129520		choikiwon	Dangerous Skating (JOI16_skating)	C++17	100 / 100	946 ms	125424 KiB

skating

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

typedef pair<int, int> pii;

const int MN = 1010;

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

int R, C;
char G[MN][MN];
pii S, T;

int cc[MN][MN][4];
int dp(int r, int c, int d) {
    int &ret = cc[r][c][d];
    if(ret != -1) return ret;

    int nr = r + dy[d];
    int nc = c + dx[d];
    if(G[nr][nc] == '#') return ret = r * C + c;
    else return ret = dp(nr, nc, d);
}

vector<pii> adj[MN * MN];
priority_queue<pii> pq;
int dist[MN * MN];

void dijkstra(int s) {
    for(int i = 0; i < R * C; i++) dist[i] = 1e9;
    pq.push(pii(0, s));
    dist[s] = 0;
    while(!pq.empty()) {
        int u = pq.top().second;
        int ud = -pq.top().first;
        pq.pop();

        if(dist[u] < ud) continue;

        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;

            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push(pii(-dist[v], v));
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> R >> C;

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> G[i][j];
        }
    }

    cin >> S.first >> S.second >> T.first >> T.second;
    S.first--;
    S.second--;
    T.first--;
    T.second--;

    memset(cc, -1, sizeof(cc));

    for(int i = 1; i < R - 1; i++) {
        for(int j = 1; j < C - 1; j++) {
            for(int k = 0; k < 4; k++) {
                int ni = i + dy[k];
                int nj = j + dx[k];
                if(G[ni][nj] == '#') continue;

                adj[i * C + j].push_back(pii(ni * C + nj, 2));
                adj[i * C + j].push_back(pii(dp(i, j, k), 1));
            }
        }
    }

    dijkstra(S.first * C + S.second);

    if(dist[T.first * C + T.second] == 1e9) cout << -1;
    else cout << dist[T.first * C + T.second];
}

Compilation message (stderr)

skating.cpp: In function 'void dijkstra(int)':
skating.cpp:41:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22