Submission #523010

#	Time	Username	Problem	Language	Result	Execution time	Memory
523010		Deepesson	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	515 ms	44396 KiB

skyscraper

#include <bits/stdc++.h>
#define MAX 31000
typedef std::pair<int,int> pii; ///Skyscraper .first, level .second
std::map<pii,std::vector<pii>> con;
typedef std::pair<pii,int> ppi;
typedef std::bitset<sizeof(pii)*8> bits;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::unordered_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(count==1e6)break;
        if(__.first<0||__.first>=N)continue;
        if(visitou.find(*((bits*)&__))!=visitou.end())continue;
        visitou.insert(*((bits*)&__));
        ++count;
        if(__==fim){
            std::cout<<___.second<<"\n";
            return 0;
        }
        deque.push_back({{__.first+__.second,__.second},___.second+1});
        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:37:27: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
   37 |         if(visitou.find(*((bits*)&__))!=visitou.end())continue;
      |                          ~^~~~~~~~~~~
skyscraper.cpp:38:26: warning: dereferencing type-punned pointer will break strict-aliasing rules [-Wstrict-aliasing]
   38 |         visitou.insert(*((bits*)&__));
      |                         ~^~~~~~~~~~~

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