제출 #612597

#제출 시각아이디문제언어결과실행 시간메모리
612597JomnoiJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1095 ms87768 KiB
#include <bits/stdc++.h> using namespace std; const short MAX_N = 30000; short B[MAX_N], P[MAX_N]; unordered_map <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()); } queue <pair <short, short>> q; q.emplace(B[0], P[0]); dist[B[0]][P[0]] = 0; while(!q.empty()) { short b = q.front().first, p = q.front().second; q.pop(); if(b == B[1]) { cout << dist[b][p]; return 0; } if(b - p >= 0 and !dist[b - p].count(p)) { dist[b - p][p] = dist[b][p] + 1; q.emplace(b - p, p); } if(b + p < N and !dist[b + p].count(p)) { dist[b + p][p] = dist[b][p] + 1; q.emplace(b + p, p); } for(short p2 : graph[b]) { if(b - p2 >= 0 and !dist[b - p2].count(p2)) { dist[b - p2][p2] = dist[b][p] + 1; q.emplace(b - p2, p2); } if(b + p2 < N and !dist[b + p2].count(p2)) { dist[b + p2][p2] = dist[b][p] + 1; q.emplace(b + p2, 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...