제출 #1130391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130391		Ludissey	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1098 ms	48968 KiB

skyscraper

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<unordered_set<int>> neigh(N);
    int sb=-1,se=-1;
    for (int i = 0; i < M; i++)
    {
        int B,P; cin >> B >> P;
        if(sb==-1) sb=B;
        else if(se==-1) se=B;
        neigh[B].insert(P);
    }
    int sq=sqrt(N);
    vector<vector<int>> dist(N,vector<int>(sq,1e9));
    vector<vector<int>> visited(N,vector<int>(sq,0));
    priority_queue<pair<int,pair<int,int>>> q;
    q.push({0,{sb,0}});
    dist[sb][0]=0;
    while(!q.empty()){
        int x=q.top().second.first,s=q.top().second.second; q.pop();
        if(visited[x][s]) continue;
        visited[x][s]=true;
        int d=dist[x][s];
        if(s>0){
            if(x-s>=0) {
                if(dist[x-s][s]>d+1){
                    dist[x-s][s]=d+1;
                    if(!visited[x-s][s]) q.push({-(d+1),{x-s,s}});
                }
            }
            if(x+s<N){
                if(dist[x+s][s]>d+1){
                    dist[x+s][s]=d+1;
                    if(!visited[x+s][s]) q.push({-(d+1),{x+s,s}});
                }
            }
        }
        for (auto u : neigh[x])
        {
            if(u==s) continue;
            if(u>=sq){
                int c=d+1;
                for (int j = x+u; j < N; j+=u)
                {
                     if(dist[j][0]>c){
                        dist[j][0]=c;
                        if(!visited[j][0]) q.push({-(c),{j,0}});
                    }
                    c++;
                }
                c=d+1;
                for (int j = x-u; j >= 0; j-=u)
                {
                     if(dist[j][0]>c){
                        dist[j][0]=c;
                        if(!visited[j][0]) q.push({-(c),{j,0}});
                    }
                    c++;
                }
                
            }else{
                if(x-u>=0) {
                    if(dist[x-u][u]>d+1){
                        dist[x-u][u]=d+1;
                        if(!visited[x-u][u]) q.push({-(d+1),{x-u,u}});
                    }
                }
                if(x+u<N){
                    if(dist[x+u][u]>d+1){
                        dist[x+u][u]=d+1;
                        if(!visited[x+u][u]) q.push({-(d+1),{x+u,u}});
                    }
                }
            }
        }
    }
    int mn=1e9;
    for (int j = 0; j < sq; j++)
    {
        mn=min(dist[se][j],mn);
    }
    if(mn==1e9) cout << -1 << "\n";
    else cout << mn << "\n";
    return 0;
}

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