제출 #1026846

#제출 시각아이디문제언어결과실행 시간메모리
1026846Gr1senSky Walking (IOI19_walk)C++17
0 / 100
4085 ms35384 KiB
#include "walk.h" #include<vector> #include<algorithm> #include<iomanip> #include<iostream> #include<queue> #include<map> using namespace std; #define ll long long #define vi vector<ll> #define pi pair<ll, ll> #define ppi pair<pi, bool> #define pq priority_queue<ppi> #define vp vector<pi> #define mm multimap<ll, ll> struct building { ll x, h; bool visit; mm visit_yp; }; struct skyWalk { ll x1, x2, h; ll visit; ll visit_x; }; vector<building> B; vector<skyWalk> W; void oink(int p) { return; ll price = -1; auto bit = B[p].visit_yp.end(); while (bit != B[p].visit_yp.begin()) { bit--; ll temp = (*bit).second + (*bit).first; if (price == -1 || price > temp) price = temp; } cerr << price << endl; } mm fixThis(mm a) { if (a.empty()) return a; cerr << "enter fix" << endl; mm b; auto it = a.begin(); ll lcost = (*it).second, ly = (*it).first; it++; b.insert({ly, lcost}); while (it != a.end()) { ll cost = (*it).second, y = (*it).first; if (cost >= lcost + abs(y-ly)) {it++; continue;}; b.insert({y, cost}); lcost = cost; ly = y; it++; } a.clear(); it = b.end(); it--; lcost = (*it).second, ly = (*it).first; a.insert({ly, lcost}); while (it != b.begin()) { it--; ll cost = (*it).second, y = (*it).first; if (cost >= lcost + abs(y-ly)) continue; a.insert({y, cost}); lcost = cost; ly = y; } cerr << "exiting fix " << endl; return a; } ll 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) { if (s > g) swap(s, g); for (ll i = 0; i < x.size(); i++) { B.push_back({x[i], h[i], 0}); } for (ll i = 0; i < l.size(); i++) { W.push_back({B[l[i]].x, B[r[i]].x, y[i], -1}); } B[s].visit = 1; B[s].visit_yp = {{0, 0}}; //cerr << "oink" << endl; vp L; for (ll i = 0; i < B.size(); i++) { L.push_back({B[i].x, i}); } for (ll i = 0; i < W.size(); i++) { L.push_back({W[i].x1, -i-1}); L.push_back({W[i].x2, i+B.size()}); } sort(L.begin(), L.end()); mm M; cerr << "oink" << endl; for (ll i = L.size() -1; i > -1; i--) { cerr << i << " " << L[i].first << " " << L[i].second << endl; oink(g); pi a = L[i]; if (a.second < 0) { ll id = -a.second-1; auto its = M.equal_range(W[id].h); auto it = its.first, end = its.second; while (it != end) { if ((*it).second == id) { M.erase(it); break; } it++; } continue; } if (a.second >= (ll) B.size()) { ll id = a.second-B.size(); M.insert({W[id].h, id}); continue; } ll id = a.second; auto it1 = M.upper_bound(B[id].h); if (it1 == M.begin() || M.empty()) continue; auto it2 = it1; while (it2 != M.begin()) { it2--; ll wid = (*it2).second; cerr << "wid = " << wid << endl; if (W[wid].visit == -1) continue; cerr << "W[wid].visit = " << W[wid].visit << endl; B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)}); B[id].visit = 1; } if (!B[id].visit) continue; B[id].visit_yp = fixThis(B[id].visit_yp); auto bit = B[id].visit_yp.end(); bit--; while (it1 != M.begin()) { it1--; ll wid = (*it1).second; ll hi = (*it1).first; ll price = (*bit).second + abs(hi-(*bit).first); while (1) { ll temp = (*bit).second + abs(hi-(*bit).first); if (price > temp) { price = temp; if (bit != B[id].visit_yp.begin()) break; bit--; break; } break; } W[wid].visit = price; W[wid].visit_x = a.first; } } cerr << "oink" << endl; for (ll i = 0; i < L.size(); i++) { cerr << i << " " << L[i].first << " " << L[i].second << endl; oink(g); pi a = L[i]; if (a.second >= (ll) B.size()) { ll id = a.second-B.size(); auto its = M.equal_range(W[id].h); auto it = its.first, end = its.second; while (it != end) { if ((*it).second == id) { M.erase(it); break; } it++; } continue; } if (a.second < 0) { ll id = -(a.second+1); //cerr << id << endl << W[id].h << endl; M.insert({W[id].h, id}); continue; } ll id = a.second; auto it1 = M.upper_bound(B[id].h); if (it1 == M.begin() || M.empty()) continue; auto it2 = it1; while (it2 != M.begin()) { it2--; ll wid = (*it2).second; if (W[wid].visit == -1) continue; B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)}); B[id].visit = 1; } if (!B[id].visit) continue; B[id].visit_yp = fixThis(B[id].visit_yp); auto bit = B[id].visit_yp.end(); bit--; while (it1 != M.begin()) { it1--; ll wid = (*it1).second; ll hi = (*it1).first; ll price = (*bit).second + abs(hi-(*bit).first); while (1) { ll temp = (*bit).second + abs(hi-(*bit).first); if (price > temp) { price = temp; if (bit != B[id].visit_yp.begin()) break; bit--; break; } break; } W[wid].visit = price; W[wid].visit_x = a.first; } } cerr << "oink" << endl; for (ll i = L.size() -1; i > -1; i--) { cerr << i << " " << L[i].first << " " << L[i].second << endl; oink(g); pi a = L[i]; if (a.second < 0) { ll id = -a.second-1; auto its = M.equal_range(W[id].h); auto it = its.first, end = its.second; while (it != end) { if ((*it).second == id) { M.erase(it); break; } it++; } continue; } if (a.second >= (ll) B.size()) { ll id = a.second-B.size(); M.insert({W[id].h, id}); continue; } ll id = a.second; auto it1 = M.upper_bound(B[id].h); if (it1 == M.begin() || M.empty()) continue; auto it2 = it1; while (it2 != M.begin()) { it2--; ll wid = (*it2).second; if (W[wid].visit == -1) continue; B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)}); B[id].visit = 1; } if (!B[id].visit) continue; B[id].visit_yp = fixThis(B[id].visit_yp); auto bit = B[id].visit_yp.end(); bit--; while (it1 != M.begin()) { it1--; ll wid = (*it1).second; ll hi = (*it1).first; ll price = (*bit).second + abs(hi-(*bit).first); while (1) { ll temp = (*bit).second + abs(hi-(*bit).first); if (price > temp) { price = temp; if (bit != B[id].visit_yp.begin()) break; bit--; break; } break; } W[wid].visit = price; W[wid].visit_x = a.first; } } ll price = -1; auto bit = B[g].visit_yp.end(); while (bit != B[g].visit_yp.begin()) { bit--; ll temp = (*bit).second + (*bit).first; if (price == -1 || price > temp) price = temp; } return price; } /* int main() { 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; long long result = min_distance(x, h, l, r, y, s, g); cout << result << "\n"; } //*/

컴파일 시 표준 에러 (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:83:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (ll i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:86:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (ll i = 0; i < l.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:95:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<building>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (ll i = 0; i < B.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<skyWalk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (ll i = 0; i < W.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:169:19: 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]
  169 |  for (ll i = 0; i < L.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...