제출 #418128

#제출 시각아이디문제언어결과실행 시간메모리
418128usachevd0Sky Walking (IOI19_walk)C++17
24 / 100
3284 ms840888 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "walk.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const ll INF64 = 1e18; const int maxN = 100005; int n, m; const int maxV = 4e6 + 6; int V; vector<pii> G[maxV]; ll dist[maxV]; priority_queue<pli> pq; map<int, int> ptIdx[maxN]; int getIdx(int x, int y) { if (ptIdx[x].count(y)) return ptIdx[x][y]; // debug(x, y, V); return ptIdx[x][y] = V++; } void addEdge(int u, int v, int w) { // debug(u, v, w); G[u].emplace_back(v, w); G[v].emplace_back(u, w); } ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int SI, int TI) { n = X.size(), m = L.size(); int S, T; for (int i = 0; i < n; ++i) { int v = getIdx(i, 0); if (i == SI) S = v; if (i == TI) T = v; } // debug(S, T); vector<int> ordy(m); iota(all(ordy), 0); sort(all(ordy), [&](int j1, int j2) -> bool { return Y[j1] > Y[j2]; }); vector<int> ordh(n); iota(all(ordh), 0); sort(all(ordh), [&](int i1, int i2) -> bool { return H[i1] > H[i2]; }); set<int> active; int hptr = 0; for (int j : ordy) { int l = L[j], r = R[j], y = Y[j]; for (; hptr < ordh.size(); ++hptr) { int i = ordh[hptr]; if (H[i] >= y) active.insert(i); else break; } int last_i = l, last_v = getIdx(l, y); for (auto it = active.upper_bound(l); it != active.end() && (*it) <= r; it = next(it)) { int i = *it; int v = getIdx(i, y); addEdge(last_v, v, X[i] - X[last_i]); last_v = v; last_i = i; } // for (int i = l + 1; i <= r; ++i) { // if (H[i] >= y) { // int v = getIdx(i, y); // addEdge(last_v, v, X[i] - X[last_i]); // last_v = v; // last_i = i; // } // } } for (int i = 0; i < n; ++i) { int last_y = -1, last_v = -1; for (auto& [y, v] : ptIdx[i]) { if (last_y != -1) { addEdge(last_v, v, y - last_y); } last_y = y; last_v = v; } } fill(dist, dist + V, INF64); dist[S] = 0; pq.push({0, S}); while (!pq.empty()) { ll _d = -pq.top().fi; int v = pq.top().se; pq.pop(); if (_d != dist[v]) continue; // debug(v, dist[v]); if (v == T) return dist[v]; for (auto& [u, w] : G[v]) if (chkmin(dist[u], dist[v] + w)) pq.push({-dist[u], u}); } return -1; } #ifdef LOCAL int32_t main() { #ifdef LOCAL freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n, m; assert(2 == scanf("%d%d", &n, &m)); vector<int> x(n), h(n); for (int i = 0; i < n; i++) assert(2 == scanf("%d%d", &x[i], &h[i])); vector<int> l(m), r(m), y(m); for (int i = 0; i < m; i++) assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i])); int s, g; assert(2 == scanf("%d%d", &s, &g)); fclose(stdin); long long result = min_distance(x, h, l, r, y, s, g); printf("%lld\n", result); fclose(stdout); return 0; } #endif

컴파일 시 표준 에러 (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:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (; hptr < ordh.size(); ++hptr) {
      |                ~~~~~^~~~~~~~~~~~~
walk.cpp:151:9: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |         if (v == T) return dist[v];
      |         ^~
#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...