제출 #564927

#제출 시각아이디문제언어결과실행 시간메모리
564927flappybirdJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1090 ms3156 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define MAX 40100 #define MAXS 20 #define INF 1010101010 #define bb ' ' #define ln '\n' #define Ln '\n' vector<pii> adj[MAX]; int B[MAX]; int P[MAX]; vector<int> locset; vector<int> locs[MAX]; int N, M; int findpv(int x) { int ind = upper_bound(locset.begin(), locset.end(), x) - locset.begin(); ind--; if (ind < 0) return -1; else return locset[ind]; } int findnx(int x) { int ind = lower_bound(locset.begin(), locset.end(), x) - locset.begin(); if (ind >= M) return -1; else return locset[ind]; } int np(int x, int p) { return x / p * p + p; } int dist[MAX]; int vis[MAX]; vector<int> locp[MAX]; bool chk(vector<int>& v, int p) { int ind = lower_bound(v.begin(), v.end(), p) - v.begin(); if (ind >= v.size() || v[ind] != p) return false; return true; } signed main() { ios::sync_with_stdio(false), cin.tie(0); cin >> N >> M; int i; for (i = 0; i < M; i++) cin >> B[i] >> P[i], locset.emplace_back(B[i]), locs[B[i]].push_back(i), locp[B[i]].push_back(P[i]); for (i = 0; i < N; i++) sort(locp[i].begin(), locp[i].end()); sort(locset.begin(), locset.end()); locset.erase(unique(locset.begin(), locset.end()), locset.end()); int j; for (i = 0; i < N; i++) { for (j = 1; j < locs[i].size(); j++) { adj[locs[i][j]].emplace_back(locs[i][j - 1], 0); adj[locs[i][j - 1]].emplace_back(locs[i][j], 0); } } for (i = 0; i < M; i++) { int delta = 1; while (1) { int loc = findpv(B[i] - delta); if (loc == -1) break; bool found = false; if ((B[i] - loc) % P[i] == 0) { if (chk(locp[loc], P[i])) { adj[i].emplace_back(locs[loc][0], (B[i] - loc) / P[i]); found = true; } else { for (auto v : locs[loc]) adj[i].emplace_back(v, (B[i] - loc) / P[i]); } } if (found) break; delta = B[i] - loc; delta = np(delta, P[i]); } delta = 1; while (1) { int loc = findnx(B[i] + delta); if (loc == -1) break; bool found = false; if ((loc - B[i]) % P[i] == 0) { if (chk(locp[loc], P[i])) { adj[i].emplace_back(locs[loc][0], (loc - B[i]) / P[i]); found = true; } else { for (auto v : locs[loc]) adj[i].emplace_back(v, (loc - B[i]) / P[i]); } } if (found) break; delta = loc - B[i]; delta = np(delta, P[i]); } } for (i = 1; i < M; i++) dist[i] = INF; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(0, 0); while (pq.size()) { int v = pq.top().second; pq.pop(); if (vis[v]) continue; vis[v] = 1; for (auto& [x, c] : adj[v]) { if (vis[x]) continue; if (dist[x] > dist[v] + c) { dist[x] = dist[v] + c; pq.emplace(dist[x], x); } } } if (dist[1] >= INF) dist[1] = -1; cout << dist[1] << Ln; }

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

skyscraper.cpp: In function 'bool chk(std::vector<int>&, int)':
skyscraper.cpp:40:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  if (ind >= v.size() || v[ind] != p) return false;
      |      ~~~~^~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (j = 1; j < locs[i].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~~
#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...