제출 #1048965

#제출 시각아이디문제언어결과실행 시간메모리
1048965dozerSky Walking (IOI19_walk)C++14
10 / 100
4046 ms357584 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n" #define pb push_back #define pii pair<ll, ll> #define st first #define nd second #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define LL node * 2 #define RR node * 2 + 1 #define ll long long long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { ll n = x.size(), m = l.size(); vector<map<ll, long long>> dist(n); vector<vector<pii>> adj(n); vector<vector<ll>> points(n); vector<array<ll, 3>> events; vector<ll> last(m, -1); set<pii> open; for (ll i = 0; i < m; i++) events.pb({l[i], i, -1}), events.pb({r[i] + 1, i, 1}); sort(events.begin(), events.end()); ll it = 0; for (ll i = 0; i < n; i++){ while(it < events.size() && events[it][0] == i){ ll t = events[it][2], ind = events[it][1]; if (t == -1) open.insert({-y[ind], ind}); else open.erase({-y[ind], ind}); it++; } auto it2 = open.lower_bound({-h[i], 0}); while(it2 != open.end()){ points[i].pb(-it2->st); ll ind = it2->nd; if (last[ind] != -1){ adj[i].pb({y[ind], last[ind]}); adj[last[ind]].pb({y[ind], i}); } last[ind] = i; it2++; } points[i].pb(0); } for (ll i = 0; i < n; i++){ sort(points[i].begin(), points[i].end()); sort(adj[i].begin(), adj[i].end()); } priority_queue<array<long long, 3>> q; q.push({0, s, 0}); dist[s][0] = 0; while(!q.empty()){ array<ll, 3> tmp = q.top(); q.pop(); long long X = tmp[1], y = tmp[2], d = -tmp[0]; if (dist[X][y] < d) continue; //cout<<X<<sp<<y<<sp<<d<<endl; ll pos = lower_bound(points[X].begin(), points[X].end(), y) - points[X].begin(); if (pos > 0){ ll to = points[X][pos - 1]; ll tmp = d + abs(to - y); if (dist[X].count(to) == 0 || dist[X][to] > tmp){ dist[X][to] = tmp; q.push({-tmp, X, to}); } } if (pos < points[X].size()){ ll to = points[X][pos + 1]; ll tmp = d + abs(to - y); if (dist[X].count(to) == 0 || dist[X][to] > tmp){ dist[X][to] = tmp; q.push({-tmp, X, to}); } } pos = lower_bound(adj[X].begin(), adj[X].end(), make_pair(y, (ll)0)) - adj[X].begin(); while(pos < adj[X].size() && adj[X][pos].st == y){ ll to = adj[X][pos].nd; ll tmp = d + (ll)abs(x[X] - x[to]); if (dist[to].count(y) == 0 || dist[to][y] > tmp){ dist[to][y] = tmp; q.push({-tmp, to, y}); } pos++; } } if (dist[g].count(0)) return dist[g][0]; return -1; } /* int main() { fileio(); 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; }*/

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

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:34:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   while(it < events.size() && events[it][0] == i){
      |         ~~~^~~~~~~~~~~~~~~
walk.cpp:78:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if (pos < points[X].size()){
      |       ~~~~^~~~~~~~~~~~~~~~~~
walk.cpp:88:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   while(pos < adj[X].size() && adj[X][pos].st == y){
      |         ~~~~^~~~~~~~~~~~~~~
#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...