제출 #761425

#제출 시각아이디문제언어결과실행 시간메모리
761425MinaRagy06Sky Walking (IOI19_walk)C++17
10 / 100
4061 ms588960 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> intersect[100'005]; vector<array<int, 3>> adj[100'005]; vector<ll> dist[100'005]; vector<int> idx[100'005]; int sparse[17][200'005]; const ll INF = 1e18; ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) { int n = x.size(), m = l.size(); for (int i = 0; i < n; i++) { sparse[0][i] = h[i]; } for (int j = 1; j < 17; j++) { for (int i = 0; i < n; i++) { sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]); } } y.push_back(0); idx[s].push_back(m); dist[s].push_back(INF); for (int i = 0; i < m; i++) { int j = l[i]; while (j <= r[i]) { if (y[i] <= h[j]) { intersect[i].push_back(j); j++; continue; } int mx = 0; for (int k = 16; k >= 0; k--) { if (y[i] > max(mx, sparse[k][j])) { mx = max(mx, sparse[k][j]); j += (1 << k); } } if (j <= r[i]) { intersect[i].push_back(j); j++; } } for (int k = 0; k < intersect[i].size(); k++) { dist[intersect[i][k]].push_back(INF); idx[intersect[i][k]].push_back(i); } for (int k = 0; k < intersect[i].size(); k++) { if (k + 1 < intersect[i].size()) { adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k + 1], idx[intersect[i][k + 1]].size() - 1, y[i]}); } if (k - 1 >= 0) { adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k - 1], idx[intersect[i][k - 1]].size() - 1, y[i]}); } } // assert(intersect[i].size() <= 10); } int cnt = 0; for (int i = 0; i < n; i++) { cnt += idx[i].size(); } assert(cnt <= 2'000'000); priority_queue<pair<ll, array<int, 3>>> pq; pq.push({0, {s, 0, 0}}); while (pq.size()) { ll d = -pq.top().first; int i = pq.top().second[0]; int j = pq.top().second[1]; int cury = pq.top().second[2]; pq.pop(); if (d > dist[i][j]) continue; cnt++; for (auto [nxt, nxth, w] : adj[i]) { ll newd = d + abs(x[nxt] - x[i]) + abs(cury - w); if (newd < dist[nxt][nxth]) { dist[nxt][nxth] = newd; pq.push({-newd, {nxt, nxth, w}}); } } } ll ans = INF; for (int i = 0; i < dist[g].size(); i++) { ans = min(ans, dist[g][i] + y[idx[g][i]]); } // for (auto i : dist[g]) { // ans = min(ans, i.first + i.second); // } if (ans >= INF) return -1; return ans; } // int main() { // ios_base::sync_with_stdio(0), cin.tie(0); // int N, M; // cin >> N >> M; // vector<int> X(N), H(N); // for (int i = 0; i < N; i++) { // cin >> X[i] >> H[i]; // } // vector<int> L(M), R(M), Y(M); // for (int i = 0; i < M; i++) { // cin >> L[i] >> R[i] >> Y[i]; // } // int S, G; // cin >> S >> G; // cout << min_distance(X, H, L, R, Y, S, G) << '\n'; // return 0; // }

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

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int k = 0; k < intersect[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             if (k + 1 < intersect[i].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
walk.cpp:50:118: warning: narrowing conversion of '(idx[intersect[i].std::vector<int>::operator[](((std::vector<int>::size_type)(k + 1)))].std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   50 |                 adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k + 1], idx[intersect[i][k + 1]].size() - 1, y[i]});
      |                                                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
walk.cpp:53:118: warning: narrowing conversion of '(idx[intersect[i].std::vector<int>::operator[](((std::vector<int>::size_type)(k - 1)))].std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   53 |                 adj[intersect[i][k]].push_back((array<int, 3>) {intersect[i][k - 1], idx[intersect[i][k - 1]].size() - 1, y[i]});
      |                                                                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
walk.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < dist[g].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...