제출 #31245

#제출 시각아이디문제언어결과실행 시간메모리
31245nibnalinJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
0 ms4372 KiB
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <cmath> #include <algorithm> using namespace std; const int inf = int(1e9)+5, maxn = int(3e4)+5; int D[maxn][2]; vector<pair<int, int>> A; vector<int> graph[maxn]; set<pair<int, int>> doge[maxn]; // 0 => doge // 1 => skyscraper bool go(int x, int y) { if(A[x].first == y) return 1; auto it = doge[y].lower_bound({A[x].second, -1}); return (it == doge[y].end() && it->first != A[x].second); } int main(void) { int n, m; scanf("%d%d", &n, &m); A.clear(); A.resize(m); for(int i = 0;i < m;i++) scanf("%d%d", &A[i].first, &A[i].second), D[i][0] = inf; pair<int, int> dest = A[1], strt = A[0]; int s, t; for(int i = 0;i < n;i++) D[i][1] = inf; sort(A.begin(), A.end()); A.resize(int(unique(A.begin(), A.end())-A.begin())); m = int(A.size()); for(int i = 0;i < m;i++) { if(strt == A[i]) s = i; if(dest == A[i]) t = i; } for(int i = 0;i < m;i++) { doge[A[i].first].insert({A[i].second, i}); } for(int i = 0;i < m;i++) { for(int j = A[i].first;j < n;j += A[i].second) { if(go(i, j)) graph[i].push_back(j); else { graph[i].push_back(j); break; } } for(int j = A[i].first;j >= 0;j -= A[i].second) { if(go(i, j)) graph[i].push_back(j); else { graph[i].push_back(j); break; } } } set<pair<int, pair<int, int>>> Q; Q.insert({0, {s, 0}}); D[s][0] = 0; while(!Q.empty()) { pair<int, pair<int, int>> top = *Q.begin(); Q.erase(Q.begin()); //cout << top.first << " " << top.second.first << " " << top.second.second << "\n"; if(top.second.second) { for(auto it: doge[top.second.first]) { if(D[it.second][0] > top.first) { if(D[it.second][0] != inf) Q.erase({D[it.second][0], {it.second, 0}}); D[it.second][0] = top.first; Q.insert({D[it.second][0], {it.second, 0}}); } } } else { for(auto it: graph[top.second.first]) { int c = top.first+abs(it-A[top.second.first].first)/A[top.second.first].second; if(D[it][1] > c) { if(D[it][1] != inf) Q.erase({D[it][1], {it, 1}}); D[it][1] = c; Q.insert({D[it][1], {it, 1}}); } } } } printf("%d\n", (D[t][0] == inf)?-1:D[t][0]); }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
skyscraper.cpp:31:85: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0;i < m;i++) scanf("%d%d", &A[i].first, &A[i].second), D[i][0] = inf;
                                                                                     ^
skyscraper.cpp:78:16: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     D[s][0] = 0;
                ^
skyscraper.cpp:112:27: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%d\n", (D[t][0] == inf)?-1:D[t][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...