Submission #1244038

#TimeUsernameProblemLanguageResultExecution timeMemory
1244038pumkinheadJakarta Skyscrapers (APIO15_skyscraper)C++20
10 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; const int SQRT = 1.7e2; struct BfsElem{ int node, dir, dist; }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; vector<vector<bool>> visited(n, vector<bool>(SQRT, false)); vector<vector<int>> doges(n); int targetBuilding; for(int i=0; i<m; i++){ int b, p; cin>>b>>p; if(i == 1){ targetBuilding = b; } doges[b].push_back(p); } queue<BfsElem> bfs; bfs.push({0, 0, 0}); int ans = -1; int mults[2] = {1, -1}; while(bfs.size()){ BfsElem elem = bfs.front(); bfs.pop(); if(elem.node < 0 || n <= elem.node) continue; if(elem.node == targetBuilding){ ans = elem.dist; break; } if(abs(elem.dir) < SQRT){ if(visited[elem.node][abs(elem.dir)]) continue; visited[elem.node][abs(elem.dir)] = true; } while(doges[elem.node].size()){ for(int mult : mults){ int newDir = mult * doges[elem.node].back(); bfs.push({elem.node + newDir, newDir, elem.dist + 1}); } doges[elem.node].pop_back(); } if(elem.dir != 0){ bfs.push({elem.node + elem.dir, elem.dir, elem.dist + 1}); } } cout<<ans; }
#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...