Submission #839356

#	Time	Username	Problem	Language	Result	Execution time	Memory
839356		drkarlicio2107	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	431 ms	12296 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int n, m; const int SQ=10;
vector <int> pos [30010];
pair <int, int> l [30010];
int sol [30010][SQ+10];
int bio [30010][SQ+10];
typedef pair < int, pair <int, int> > byk;
priority_queue < byk, vector <byk>, greater <byk> > s;
int main(){
    ios_base::sync_with_stdio (false);
    cin.tie (0);
    cin >> n >> m;
    for (int i=0; i<m; i++) cin >> l [i].first >> l [i].second;
    for (int i=0; i<m; i++) pos [l [i].first].push_back (l [i].second);
    for (int i=0; i<n; i++){
        for (int j=0; j<SQ+1; j++){
            sol [i][j]=1e9;
            s.push ({1e9, {i, j}});
        }
    }
    s.push ({0, {l [0].first, l [0].second}});
    sol [l [0].first][l [0].second]=0;
    while (!s.empty ()){
        byk tp = s.top();
        int res=tp.first;
        if (res==1e9) break;
        int x=tp.second.first;
        int p=tp.second.second;
        s.pop();
        //cout << res << " " << x << " " << p << endl;
        bio [x][p]=1;
        //cout << res << " " << x << " " << p << endl;
        int siz = pos[x].size();
        for (int i=0; i<siz; i++){
            int po=pos [x][i];
            if (po>SQ){
                for (int j=x+po; j<n; j+=po){
                    if (sol [j][0]<=(j-x)/po+res || bio [j][0]) continue;
                    s.push ({sol [j][0]=(j-x)/po+res, {j, 0}});
                }
                for (int j=x-po; j>=0; j-=po){
                    if (sol [j][0]<=(x-j)/po+res  || bio [j][0]) continue;
                    s.push ({sol [j][0]=(x-j)/po+res, {j, 0}});
                }
            }
            else {
                if (x-po>=0){
                    if (sol [x-po][po]>1+res && !bio [x-po][po]) {
                        sol [x-po][po]=1+res;
                        s.push ({sol [x-po][po], {x-po, po}});
                    }
                }
                if (x+po<n){
                    if (sol [x+po][po]>1+res && !bio [x+po][po]) {
                        sol [x+po][po]=1+res;
                        s.push ({sol [x+po][po], {x+po, po}});
                    }
                }
            }
        }
        if (x-p>=0 && p!=0){
            if (sol [x-p][p]>1+res && !bio [x-p][p]) {
                sol [x-p][p]=1+res;
                s.push ({sol [x-p][p], {x-p, p}});
            }
        }
        if (x+p<n && p!=0){
            if (sol [x+p][p]>1+res && !bio [x+p][p]) {
                sol [x+p][p]=1+res;
                s.push ({sol [x+p][p], {x+p, p}});
            }
        }
    }
    int so=1e9;
    for (int i=0; i<SQ+1; i++) so=min (so,  sol [l [1].first][i]);
    if (so==1e9) cout << -1;
    else cout << so;
}

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