Submission #523023

#	Time	Username	Problem	Language	Result	Execution time	Memory
523023		Deepesson	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1097 ms	66496 KiB

skyscraper

#include <bits/stdc++.h>
#define MAX 31000
typedef std::pair<short,short> pii; ///Skyscraper .first, level .second
typedef std::pair<pii,int> ppi;
typedef int bits;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::set<bits> visitou;
    int N,M;
    std::cin>>N>>M;
    bool cachorro[N]={};
    std::vector<int> poder[N];
    int ha[M],hb[M];
    for(int i=0;i!=M;++i){
        int a,b;
        std::cin>>a>>b;
        cachorro[a]=true;
        poder[a].push_back(b);
        ha[i]=a;
        hb[i]=b;
    }
    pii origem = {ha[0],hb[0]};
    pii fim = {ha[1],hb[1]};
    std::deque<ppi> deque;
    deque.push_back({origem,0});
    int count=0;
    while(deque.size()){
        auto ___ = deque.front();
        auto __ = ___.first;
        deque.pop_front();
        if(__.first<0||__.first>=N)continue;
        if(!visitou.insert(*((bits*)&__)).second)continue;
        if(__==fim){
            std::cout<<___.second<<"\n";
            return 0;
        }
        if(__.first+__.second<N)
        deque.push_back({{__.first+__.second,__.second},___.second+1});
        if(__.first-__.second>=0)
        deque.push_back({{__.first-__.second,__.second},___.second+1});
        if(cachorro[__.first]){
            cachorro[__.first]=false;
            for(auto&x:poder[__.first])
            deque.push_front({{__.first,x},___.second});
        }
    }
    std::cout<<"-1\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:35:30: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
   35 |         if(!visitou.insert(*((bits*)&__)).second)continue;
      |                             ~^~~~~~~~~~~
skyscraper.cpp:29:9: warning: unused variable 'count' [-Wunused-variable]
   29 |     int count=0;
      |         ^~~~~

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