Submission #49030

#	Time	Username	Problem	Language	Result	Execution time	Memory
49030		someone_aa	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	228 ms	26748 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 2100;
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;
    visited[st[0]][p[0]]=true;

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

        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));
            }
        }
    }
    int result = INT_MAX;
    for(int i=0;i<maxn;i++) {
        if(visited[st[1]][i]) result = min(result, dist[st[1]][i]);
    }
    if(result == INT_MAX) cout<<"-1\n";
    else cout<<result<<"\n";
    return 0;
}

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