Submission #14411

#TimeUsernameProblemLanguageResultExecution timeMemory
14411gs14004Jakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
30 ms119884 KiB
#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <utility> #include <queue> using namespace std; typedef pair<int,int> pi; const int B = 150; int m, n; bool r_dir[30005][B], l_dir[30005][B]; bool vis[30005 * B]; vector<pi> graph[30005 * B]; priority_queue<pi,vector<pi>,greater<pi> > pq; int dijkstra(int st, int ed){ pq.push(pi(0,st)); while (!pq.empty()) { pi t = pq.top(); pq.pop(); if(t.second == ed){ return t.first; } if(vis[t.second]) continue; vis[t.second] = 1; for (auto &i : graph[t.second]){ if(!vis[i.second]) pq.push(pi(i.first + t.first,i.second)); } } return -1; } int main(){ int st = 0, ed = 0; scanf("%d %d",&n,&m); for (int i=0; i<m; i++) { int x,y; scanf("%d %d",&x,&y); if(i == 0){ st = x; } else if(i == 1){ ed = x; } if(y < B){ r_dir[x][y] = 1; l_dir[x][y] = 1; graph[x].push_back(pi(0,x + n * y)); } else{ for (int j=1; x - j * y >= 0; j++) { graph[x].push_back(pi(j,x - j * y)); } for (int j=1; x + j * y < n; j++) { graph[x].push_back(pi(j,x + j * y)); } } } for (int i=1; i<3; i++) { for (int j=i; j<n; j++) { r_dir[j][i] |= r_dir[j - i][i]; } for (int j=n-i-1; j>=0; j--) { l_dir[j][i] |= l_dir[j + i][i]; } for (int j=0; j<n; j++) { if(r_dir[j][i] && j + i < n){ graph[i * n + j].push_back(pi(1,i * n + j + i)); } if(l_dir[j][i] && j - i >= 0){ graph[i * n + j].push_back(pi(1,i * n + j - i)); } graph[i * n + j].push_back(pi(0,j)); } } printf("%d",dijkstra(st,ed)); }
#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...