Submission #45494

#TimeUsernameProblemLanguageResultExecution timeMemory
45494dqhungdlJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; int n,m,d[2005][30005]; bool Visited[30005],Free[2005][30005]; vector<int> g[30005]; queue<ii> Q; int main() { ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); cin>>n>>m; int pos,step; while(m--) { cin>>pos>>step; g[pos+1].push_back(step); } for(int i=0; i<g[1].size(); i++) { Free[1][g[1][i]]=true; Q.push(ii(1,g[1][i])); } while(Q.size()>0) { int u=Q.front().first; int v=Q.front().second; Q.pop(); if(u==2) { cout<<d[u][v]; return 0; } if(Visited[u]==false) { Visited[u]=true; for(int i=0; i<g[u].size(); i++) { if(u-g[u][i]>=1&&Free[u-g[u][i]][g[u][i]]==false) { Free[u-g[u][i]][g[u][i]]=true; d[u-g[u][i]][g[u][i]]=d[u][v]+1; Q.push(ii(u-g[u][i],g[u][i])); } if(u+g[u][i]<=n&&Free[u+g[u][i]][g[u][i]]==false) { Free[u+g[u][i]][g[u][i]]=true; d[u+g[u][i]][g[u][i]]=d[u][v]+1; Q.push(ii(u+g[u][i],g[u][i])); } } } if(u-v>=1&&Free[u-v][v]==false) { Free[u-v][v]=true; d[u-v][v]=d[u][v]+1; Q.push(ii(u-v,v)); } if(u+v<=n&&Free[u+v][v]==false) { Free[u+v][v]=true; d[u+v][v]=d[u][v]+1; Q.push(ii(u+v,v)); } } cout<<-1; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<g[1].size(); i++)
                  ~^~~~~~~~~~~~
skyscraper.cpp:39:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<g[u].size(); i++)
                          ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...