Submission #695180

#TimeUsernameProblemLanguageResultExecution timeMemory
695180HossamHero7Jakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
1104 ms243816 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' void solve(){ int n,m; cin>>n>>m; vector<vector<int>> adj(n+1); vector<pair<int,int>> v(m); int pos = 0; for(int i=0;i<m;i++){ int a,b;cin>>a>>b; v[i].first = a; v[i].second = b; if(i == 1) pos = a; adj[a].push_back(i); } queue<pair<int,int>> q; vector<vector<bool>> vis(n,vector<bool>(m)); q.push({v[0].first,0}); vector<vector<int>> dis(n,vector<int>(m,0)); while(q.size()){ pair<int,int> cur = q.front(); q.pop(); for(auto ch : adj[cur.first]){ int p = v[ch].second; if(cur.first+p<n && !vis[cur.first+p][ch]){ q.push({cur.first+p,ch}); dis[cur.first+p][ch] = dis[cur.first][cur.second] + 1; vis[cur.first+p][ch] = 1; } if(cur.first-p>=0 && !vis[cur.first-p][ch]){ q.push({cur.first-p,ch}); dis[cur.first-p][ch] = dis[cur.first][cur.second] + 1; vis[cur.first-p][ch] = 1; } } int p = v[cur.second].second; if(cur.first+p<n && !vis[cur.first+p][cur.second]){ q.push({cur.first+p,cur.second}); dis[cur.first+p][cur.second] = dis[cur.first][cur.second] + 1; vis[cur.first+p][cur.second] = 1; } if(cur.first-p>=0 && !vis[cur.first-p][cur.second]){ q.push({cur.first-p,cur.second}); dis[cur.first-p][cur.second] = dis[cur.first][cur.second] + 1; vis[cur.first-p][cur.second] = 1; } } if(v[0].first == v[1].first){ cout<<0<<endl; } else { int ans = 1e9; for(int i=0;i<m;i++){ if(i == 1) continue; if(dis[v[1].first][i] == 0) continue; ans = min(ans,dis[v[1].first][i]); } cout<<(ans==1e9?-1:ans)<<endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:11:9: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   11 |     int pos = 0;
      |         ^~~
#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...