Submission #249240

#TimeUsernameProblemLanguageResultExecution timeMemory
249240rdd6584Jakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1096 ms99832 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int ,int> pii; char visit[30000]; unordered_map<int,int> dist[30000]; int dp[30000][100]; // 거리 100 이하일 때, vector<int> v[30000]; int main() { int n, m; scanf("%d %d", &n, &m); int st, ed; for (int i = 0; i < m; i++) { int a,b; scanf("%d %d" ,&a, &b); v[a].push_back(b); if (i==0) st = a; else if (i==1) ed = a; } memset(dp, -1, sizeof(dp)); queue<pii> q; for (int i : v[st]) { if (i < 100) dp[st][i] = 0; else dist[st][i] = 0; q.push({st, i}); } while (!q.empty()) { pii tv = q.front(); q.pop(); int me; if (tv.second < 100) me = dp[tv.first][tv.second]; else me = dist[tv.first][tv.second]; if (tv.first == ed) return !printf("%d", me); int ne; if (tv.second < 100) { for (int dir = -1; dir <= 1; dir += 2) { ne = tv.first + dir * tv.second; if (ne < 0 || ne >= n) continue; if (dp[ne][tv.second] == -1) { int flag = 0; if (!visit[ne]) { visit[ne] = 1; for (int i : v[ne]) { if (i < 100) dp[ne][i] = me + 1; else dist[ne][i] = me + 1; q.push({ne, i}); flag |= i == tv.second; } } if (!flag) { q.push({ne, tv.second}); dp[ne][tv.second] = me + 1; } } } } else { for (int dir = -1; dir <= 1; dir += 2) { ne = tv.first + dir * tv.second; if (ne < 0 || ne >= n) continue; if (dist[ne].find(tv.second) == dist[ne].end()) { int flag = 0; if (!visit[ne]) { visit[ne] = 1; for (int i : v[ne]) { if (i < 100) dp[ne][i] = me + 1; else dist[ne][i] = me + 1; q.push({ne, i}); flag |= i == tv.second; } } if (!flag) { q.push({ne, tv.second}); dist[ne][tv.second] = me + 1; } } } } } printf("-1"); }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d" ,&a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:15:9: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int st, ed;
         ^~
skyscraper.cpp:40:9: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (tv.first == ed) return !printf("%d", me);
         ^~
#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...