Submission #612593

#	Time	Username	Problem	Language	Result	Execution time	Memory
612593		krit3379	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	150 ms	22800 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 30005

struct A{
    unsigned short a,b,c;
};

unsigned short a[N],p[N];
vector<unsigned short> g[N];
bitset<N> vis;
unordered_set<unsigned short> s[N];
queue<A> q;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    unsigned short n,m,i;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>a[i]>>p[i];
        g[a[i]].push_back(p[i]);
    }
    q.push({a[0],p[0],0});
    s[a[0]].insert(p[0]);
    while(!q.empty()){
        auto [x,po,w]=q.front();
        q.pop();
        if(x==a[1]){cout<<w;return 0;}
        if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
        if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
        if(vis[x])continue;
        vis[x]=true;
        for(auto po:g[x]){
            if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
            if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
        }
    }
    cout<<-1;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:47: warning: narrowing conversion of '(((int)x) - ((int)po))' from 'int' to 'short unsigned int' [-Wnarrowing]
   31 |         if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
      |                                              ~^~~
skyscraper.cpp:31:55: warning: narrowing conversion of '(((int)w) + 1)' from 'int' to 'short unsigned int' [-Wnarrowing]
   31 |         if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
      |                                                      ~^~
skyscraper.cpp:32:48: warning: narrowing conversion of '(((int)x) + ((int)po))' from 'int' to 'short unsigned int' [-Wnarrowing]
   32 |         if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
      |                                               ~^~~
skyscraper.cpp:32:56: warning: narrowing conversion of '(((int)w) + 1)' from 'int' to 'short unsigned int' [-Wnarrowing]
   32 |         if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
      |                                                       ~^~
skyscraper.cpp:36:51: warning: narrowing conversion of '(((int)x) - ((int)po))' from 'int' to 'short unsigned int' [-Wnarrowing]
   36 |             if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
      |                                                  ~^~~
skyscraper.cpp:36:59: warning: narrowing conversion of '(((int)w) + 1)' from 'int' to 'short unsigned int' [-Wnarrowing]
   36 |             if(x>=po&&!s[x-po].count(po))q.push({x-po,po,w+1}),s[x-po].insert(po);
      |                                                          ~^~
skyscraper.cpp:37:52: warning: narrowing conversion of '(((int)x) + ((int)po))' from 'int' to 'short unsigned int' [-Wnarrowing]
   37 |             if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
      |                                                   ~^~~
skyscraper.cpp:37:60: warning: narrowing conversion of '(((int)w) + 1)' from 'int' to 'short unsigned int' [-Wnarrowing]
   37 |             if(x+po<n&&!s[x+po].count(po))q.push({x+po,po,w+1}),s[x+po].insert(po);
      |                                                           ~^~

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