제출 #907368

#제출 시각아이디문제언어결과실행 시간메모리
907368yellowtoadJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
585 ms262144 KiB
#include <iostream> #include <vector> #include <queue> #define f first #define s second using namespace std; const short LIM = 200; short n, m, st, ed; int cnt, b[30001][201], u, v; vector<vector<pair<int,int>>> edge; vector<int> dist; vector<bool> vis; deque<int> q; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cnt = n-1; for (short i = 0; i < n; i++) edge.push_back({}); for (short i = 1; i <= m; i++) { cin >> u >> v; if (i == 1) st = u; if (i == 2) ed = u; if (v <= LIM) { if (!b[u][v]) { for (int j = u%v; j < n; j += v) { b[j][v] = ++cnt; edge.push_back({}); edge[cnt].push_back({j,0}); if (j != u%v) { edge[cnt].push_back({cnt-1,1}); edge[cnt-1].push_back({cnt,1}); } } } edge[u].push_back({b[u][v],0}); } else { for (int j = u%v; j < n; j += v) { ++cnt; edge.push_back({}); edge[cnt].push_back({j,0}); if (j == u) edge[u].push_back({cnt,0}); if (j != u%v) { edge[cnt].push_back({cnt-1,1}); edge[cnt-1].push_back({cnt,1}); } } } } dist.resize(cnt+1); vis.resize(cnt+1); for (int i = 0; i <= cnt; i++) dist[i] = 1e9; q.push_back(st); dist[st] = 0; while (q.size()) { int u = q.front(); q.pop_front(); if (vis[u]) continue; vis[u] = 1; if (u == ed) { cout << dist[ed] << endl; return 0; } for (int i = 0; i < edge[u].size(); i++) { if (dist[edge[u][i].f] > dist[u]+edge[u][i].s) { dist[edge[u][i].f] = dist[u]+edge[u][i].s; if (edge[u][i].s) q.push_back(edge[u][i].f); else q.push_front(edge[u][i].f); } } } cout << -1 << endl; }

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 0; i < edge[u].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
#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...