Submission #49029

#	Time	Username	Problem	Language	Result	Execution time	Memory
49029		someone_aa	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	3 ms	876 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 3100;
int dist[maxn][maxn];
bool visited[maxn][maxn];
int st[30100], p[30100], n, m;

set<int>ps[maxn];

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        cin>>st[i]>>p[i];
        ps[st[i]].insert(p[i]);
    }

    queue<pair<int,int> > q;
    q.push(mp(st[0], p[0]));
    visited[st[0]][0] = true;

    while(!q.empty()) {
        int currx = q.front().first;
        int currc = q.front().second;
        q.pop();

        if(currx == st[1]) {
            cout<<dist[currx][currx]<<"\n";
            return 0;
        }

        if(currx - currc >= 0 && !visited[currx-currc][currc]) {
            visited[currx-currc][currc] = true;
            dist[currx-currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx-currc, currc));
        }

        if(currx + currc < n && !visited[currx+currc][currc]) {
            visited[currx+currc][currc] = true;
            dist[currx+currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx+currc, currc));
        }

        for(int i: ps[currx]) {
            if(currx - i >= 0 && !visited[currx-i][i]) {
                visited[currx-i][i] = true;
                dist[currx-i][i] = dist[currx][currc] + 1;
                q.push(mp(currx-i, i));
            }
            if(currx + i < n && !visited[currx+i][i]) {
                visited[currx+i][i] = true;
                dist[currx+i][i] = dist[currx][currc] + 1;
                q.push(mp(currx+i, i));
            }
        }
    }
    cout<<-1<<"\n";
    return 0;
}

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