oj.uz

답안 #761437

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761437 2023-06-19T16:04:09 Z gun_gan Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 14 ms 21660 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 3e4 + 5, B = 175;

vector<int> g[MX];
int N, M;
int dist[MX][B];
bool vis[MX];

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);

      for(int i = 0; i < MX; i++) {
            for(int j = 0; j < B; j++) {
                  dist[i][j] = 1e9;
            }
      }
      
      cin >> N >> M;

      int s = 0, f = 0;
      for(int i = 0; i < M; i++) {
            int x, k;
            cin >> x >> k;
            g[x].push_back(k);

            if(!i) s = x;
            if(i == 1) f = x;
      }

      priority_queue<array<int,3>> pq;

      for(auto x : g[s]) {
            if(x < B) {
                  dist[s][x] = 0;
                  pq.push({dist[s][x], s, x});
            } else {
                  for(int k = 1; s + k * x < N; k++) {
                        dist[s + k * x][0] = k;
                        pq.push({-dist[s + k * x][0], s + k * x, 0}); 
                  }     

                  for(int k = 1; s - k * x >= 0; k++) {
                        dist[s - k * x][0] = k;
                        pq.push({-dist[s - k * x][0], s - k * x, 0});
                  }
            }
      }
      vis[s] = 1;

      while(!pq.empty()) {
            auto [d, v, p] = pq.top(); pq.pop();
            d = -d;

            if(d > dist[v][p]) continue;

            if(!vis[v]) {
                  for(auto x : g[v]) {
                        if(x < B) {
                              dist[v][x] = d;
                              pq.push({-dist[v][x], v, x});
                        } else {
                              for(int k = 1; v + k * x < N; k++) {
                                    if(dist[v + k * x][0] > d + k) {
                                          dist[v + k * x][0] = d + k;
                                          pq.push({-dist[v + k * x][0], v + k * x, x}); 
                                    }
                              }     

                              for(int k = 1; v - k * x >= 0; k++) {
                                    if(dist[v - k * x][0] > d + k) {
                                          dist[v - k * x][0] = d + k;
                                          pq.push({-dist[v - k * x][0], v - k * x, x});
                                    }
                              }
                        }
                  }
                  vis[v] = 1;
            }

            if(v + p < N && dist[v + p][p] > d + 1) {
                  dist[v + p][p] = d + 1;
                  pq.push({-dist[v + p][p], v + p, p});
            }

            if(v - p >= 0 && dist[v - p][p] > d + 1) {
                  dist[v - p][p] = d + 1;
                  pq.push({-dist[v - p][p], v - p, p});
            }
      }

      int ans = 1e9;
      for(int k = 0; k < B; k++) ans = min(ans, dist[f][k]);

      cout << ans << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 11 ms 21536 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Incorrect 11 ms 21588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21548 KB Output is correct
2 Correct 11 ms 21584 KB Output is correct
3 Correct 11 ms 21584 KB Output is correct
4 Incorrect 10 ms 21580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21576 KB Output is correct
2 Correct 11 ms 21536 KB Output is correct
3 Correct 11 ms 21560 KB Output is correct
4 Incorrect 10 ms 21460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21564 KB Output is correct
2 Correct 13 ms 21660 KB Output is correct
3 Correct 10 ms 21460 KB Output is correct
4 Incorrect 10 ms 21584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 21588 KB Output is correct
2 Correct 10 ms 21472 KB Output is correct
3 Correct 10 ms 21584 KB Output is correct
4 Incorrect 11 ms 21492 KB Output isn't correct
5 Halted 0 ms 0 KB -