Submission #1152921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152921		AlgorithmWarrior	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	195 ms	112312 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

int const MAX=30005;
int n,m;
int pos[MAX],pas[MAX];
bitset<MAX>vis[MAX];
bool Vis[MAX];
vector<int>puteri[MAX];

void read(){
    cin>>n>>m;
    int i;
    for(i=0;i<m;++i){
        cin>>pos[i]>>pas[i];
        puteri[pos[i]].push_back(pas[i]);
    }
}

struct traseu{
    int poz,power,len;
};

int bfs(){
    int pos0=pos[0];
    int pos1=pos[1];
    queue<traseu>q;
    for(auto put : puteri[pos0]){
        q.push({pos0,put,0});
        vis[pos0][put]=1;
    }
    Vis[pos0]=1;
    while(!q.empty()){
        auto [poz,put,len]=q.front();
        q.pop();
        if(poz==pos1)
            return len;
        if(poz-put>=0){
            if(!vis[poz-put][put]){
                vis[poz-put][put]=1;
                q.push({poz-put,put,len+1});
                if(!Vis[poz-put])
                    for(auto puter : puteri[poz-put])
                        if(!vis[poz-put][puter]){
                            vis[poz-put][puter]=1;
                            q.push({poz-put,puter,len+1});
                        }
            }
        }
        if(poz+put<n){
            if(!vis[poz+put][put]){
                vis[poz+put][put]=1;
                q.push({poz+put,put,len+1});
                if(!Vis[poz+put])
                    for(auto puter : puteri[poz+put])
                        if(!vis[poz+put][puter]){
                            vis[poz+put][puter]=1;
                            q.push({poz+put,puter,len+1});
                        }
            }
        }
    }
    return -1;
}

int main()
{
    read();
    cout<<bfs();
    return 0;
}

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