제출 #1195274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195274		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<int> B(M), P(M);
    for(int i = 0; i < M; i++){
        cin >> B[i] >> P[i];
    }

    vector<vector<int>> doges_by_pos(N);
    for(int i = 0; i < M; i++){
        doges_by_pos[B[i]].push_back(i);
    }

    int tot = N + M;
    vector<int> dist(tot, INF);
    deque<int> dq;

    dist[N + 0] = 0;
    dq.push_back(N + 0);

    vector<bool> visited_pos(N, false); // har bir pozitsiyani faqat bir marta ishlash

    while(!dq.empty()){
        int u = dq.front(); dq.pop_front();

        if(u >= N){
            int j = u - N;
            int b = B[j], p = P[j];
            for(int d = -1; d <= 1; d += 2){
                int nb = b + d * p;
                if(nb >= 0 && nb < N && dist[nb] > dist[u] + 1){
                    dist[nb] = dist[u] + 1;
                    dq.push_back(nb);
                }
            }
        } else {
            int b = u;
            if(visited_pos[b]) continue; // faqat bir marta uzatamiz
            visited_pos[b] = true;
            for(int j : doges_by_pos[b]){
                int v = N + j;
                if(dist[v] > dist[b]){
                    dist[v] = dist[b];
                    dq.push_front(v);
                }
            }
        }
    }

    int ans = dist[N + 1];
    if(ans >= INF)
        cout << -1 << "\n";
    else
        cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43