Submission #905868

#	Time	Username	Problem	Language	Result	Execution time	Memory
905868		Sir_Ahmed_Imran	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1058 ms	60624 KiB

skyscraper

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define M 30001
#define N 30001
int x[M];
int e[N];
vector<int> a[N];
vector<int> b[N];
unordered_map<int,int> vis[N];
void solve(){
    int n,m,o,p,q,r;
    cin>>n>>m;
    for(int i=o=0;i<m;i++){
        cin>>x[i]>>q;
        if(!vis[x[i]][q])
            a[x[i]].append(q);
        vis[x[i]][q]=1;
    }
    set<int> c;
    unordered_set<int> v{x[0]},u;
    while(!v.empty()){
        for(auto& i:v){
            e[i]=1;
            if(i==x[1]){
                cout<<o;
                return;
            }
        }
        for(auto& i:v){
            for(auto& j:a[i]){
                if(i>=j && !vis[i-j][j]){
                    if(e[i-j]){
                        c.insert(i-j);
                        b[i-j].append(j);
                    }
                    else a[i-j].append(j);
                    vis[i-j][j]=1;
                    u.insert(i-j);
                }
                if(i+j<n && !vis[i+j][j]){
                    if(e[i+j]){
                        c.insert(i+j);
                        b[i+j].append(j);
                    }
                    else a[i+j].append(j);
                    vis[i+j][j]=1;
                    u.insert(i+j);
                }
                if(i>=j && !a[i-j].empty() && !e[i-j])
                    u.insert(i-j);
                if(i+j<n && !a[i+j].empty() && !e[i+j])
                    u.insert(i+j);
            }
            e[i]=0;
            a[i].clear();
        }
        o++;
        for(auto& i:c){
            for(auto& j:b[i])
                a[i].append(j);
            b[i].clear();
        }
        swap(v,u);
        u.clear();
        c.clear();
    }
    cout<<-1;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:19:15: warning: unused variable 'p' [-Wunused-variable]
   19 |     int n,m,o,p,q,r;
      |               ^
skyscraper.cpp:19:19: warning: unused variable 'r' [-Wunused-variable]
   19 |     int n,m,o,p,q,r;
      |                   ^

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