제출 #1130355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130355		Ludissey	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 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()
#define int long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<vector<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].push_back(P);
    }
    int sq=sqrt(N);
    vector<vector<int>> dist(N,vector<int>(sq,1e9));
    vector<vector<int>> visited(N,vector<int>(sq,0));
    queue<pair<int,int>> q;
    q.push({sb,0});
    dist[sb][0]=0;
    while(!q.empty()){
        int x=q.front().first,s=q.front().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;
                    q.push({x-s,s});
                }
            }
            if(x+s<N){
                if(dist[x+s][s]>d+1){
                    dist[x+s][s]=d+1;
                    q.push({x+s,s});
                }
            }
        }
        int d2=(d+(s>0||(x==sb)));
        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]>d2){
                        dist[j][0]=d2;
                        q.push({j,0});
                    }
                    c++;
                }
                c=d+1;
                for (int j = x-u; j >= 0; j-=u)
                {
                     if(dist[j][0]>d2){
                        dist[j][0]=d2;
                        q.push({j,0});
                    }
                    c++;
                }
                
            }else{
                if(x-u>=0) {
                    if(dist[x-s][u]>d+d2){
                        dist[x-s][u]=d+d2;
                        q.push({x-s,u});
                    }
                }
                if(x+u<N){
                    if(dist[x+u][u]>d2){
                        dist[x+u][u]=d2;
                        q.push({x+s,u});
                    }
                }
            }
        }
    }
    int mn=1e17;
    for (int j = 0; j < sq; j++)
    {
        mn=min(dist[se][j],mn);
    }
    if(mn==1e17) cout << -1 << "\n";
    else cout << mn << "\n";
    return 0;
}

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