Submission #404991

#	Time	Username	Problem	Language	Result	Execution time	Memory
404991		Hazem	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1096 ms	72420 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 3e4+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;   
const double PI = 3.141592653589793;

multiset<int>vis[N];
queue<pair<pii,int>>que;
vector<int>vec[N];
int n,m,dis[N],vis1[N];

int bfs(int st,int end){

    que.push({{st,0},0});
    
    while(!que.empty()){
        
        int u = que.front().F.F,dis = que.front().F.S;
        int p = que.front().S;

        if(u==end)
            return dis;

        que.pop();

        vec[u].push_back(p);

        for(int i=vis1[u]?vec[u].size()-1:0;i<vec[u].size();i++){
            int x = vec[u][i];
            if(u-x>=1)
                if(vis[u-x].find(x)==vis[u-x].end())
                    que.push({{u-x,dis+1},x}),vis[u-x].insert(x);
            
            if(u+x<=n)
                if(vis[u+x].find(x)==vis[u+x].end())
                    que.push({{u+x,dis+1},x}),vis[u+x].insert(x);
        }
        
        vec[u].pop_back();
        vis1[u] = 1;
    }

    return -1;
}

int main(){

    //freopen("out.txt","w",stdout);

    scanf("%d%d",&n,&m);
    int start,end;

    for(int i=1;i<=m;i++){
        int p,pos;
        scanf("%d%d",&pos,&p);
        pos++;
        vec[pos].push_back(p);

        if(i==1)start = pos;
        if(i==2)end = pos;
    }
    
    assert(start>=1&&start<=n&&end>=1&&end<=n);
    printf("%d\n",bfs(start,end));
}   

Compilation message (stderr)

skyscraper.cpp: In function 'int bfs(int, int)':
skyscraper.cpp:38:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=vis1[u]?vec[u].size()-1:0;i<vec[u].size();i++){
      |                                             ~^~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d%d",&pos,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:74:11: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     printf("%d\n",bfs(start,end));
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:74:11: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]

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