Submission #612612

#TimeUsernameProblemLanguageResultExecution timeMemory
612612JomnoiJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
942 ms222524 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; const short MAX_N = 30000; const int MAX_W = 7350000; short qb[MAX_W], qp[MAX_W]; short B[MAX_N], P[MAX_N]; gp_hash_table <short, int> dist[MAX_N]; vector <short> graph[MAX_N]; int main() { short N, M; cin >> N >> M; for(short i = 0; i < M; i++) { cin >> B[i] >> P[i]; graph[B[i]].push_back(P[i]); } for(short i = 0; i < N; i++) { sort(graph[i].begin(), graph[i].end()); graph[i].resize(unique(graph[i].begin(), graph[i].end()) - graph[i].begin()); } int l = 0, r = 0; qb[r] = B[0]; qp[r++] = P[0]; dist[B[0]][P[0]] = 0; while(l < r) { short b = qb[l], p = qp[l++]; if(b == B[1]) { cout << dist[b][p]; return 0; } if(b - p >= 0 and dist[b - p].find(p) == dist[b - p].end()) { dist[b - p][p] = dist[b][p] + 1; qb[r] = b - p; qp[r++] = p; } if(b + p < N and dist[b + p].find(p) == dist[b + p].end()) { dist[b + p][p] = dist[b][p] + 1; qb[r] = b + p; qp[r++] = p; } for(short p2 : graph[b]) { if(b - p2 >= 0 and dist[b - p2].find(p2) == dist[b - p2].end()) { dist[b - p2][p2] = dist[b][p] + 1; qb[r] = b - p2; qp[r++] = p2; } if(b + p2 < N and dist[b + p2].find(p2) == dist[b + p2].end()) { dist[b + p2][p2] = dist[b][p] + 1; qb[r] = b + p2; qp[r++] = p2; } } } cout << -1; return 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...