제출 #218174

#제출 시각아이디문제언어결과실행 시간메모리
218174Alexa2001Sky Walking (IOI19_walk)C++17
57 / 100
683 ms170340 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> Pair; const int Nmax = 1e6 + 5; ///13:05 vector<int> x, h, l, r, y; vector<int> newl, newr, newy; vector<Pair> v[Nmax]; int nr; void add_new(int l, int r, int y) { if(l == r) return; newl.push_back(l); newr.push_back(r); newy.push_back(y); } auto cmp_buildings = [](int i, int j) { return h[i] > h[j]; }; auto cmp_skywalks = [] (int i, int j) { return y[i] > y[j]; }; void add_edge(int x, int y, int cost) { v[x].push_back({y, cost}); v[y].push_back({x, cost}); } void adjust(int node) { newl.clear(); newr.clear(); newy.clear(); int m = l.size(); vector<int> s, pref, suff; s.resize(m); pref.resize(node+1); suff.resize(h.size()-node); iota(s.begin(), s.end(), 0); iota(pref.begin(), pref.end(), 0); iota(suff.begin(), suff.end(), node); sort(s.begin(), s.end(), cmp_skywalks); sort(pref.begin(), pref.end(), cmp_buildings); sort(suff.begin(), suff.end(), cmp_buildings); int id1 = 0, id2 = 0, mx = -1, mn = h.size(); for(auto it : s) { while(id1 < pref.size() && h[pref[id1]] >= y[it]) mx = max(mx, pref[id1]), id1++; while(id2 < suff.size() && h[suff[id2]] >= y[it]) mn = min(mn, suff[id2]), id2++; if(l[it] < node && node < r[it]) { add_new(l[it], mx, y[it]); add_new(mx, mn, y[it]); add_new(mn, r[it], y[it]); } else add_new(l[it], r[it], y[it]); } swap(l, newl); swap(r, newr); swap(y, newy); } #define left_son ((node<<1)) #define right_son ((node<<1)|1) #define mid ((st+dr)>>1) class SegTree { int lazy[Nmax<<2]; public: void propag(int node) { if(!lazy[node]) return; lazy[left_son] = lazy[right_son] = lazy[node]; lazy[node] = 0; } void init() { lazy[1] = -1; } void update(int node, int st, int dr, int L, int R, int V) { if(L <= st && dr <= R) { lazy[node] = V; return; } propag(node); if(L <= mid) update(left_son, st, mid, L, R, V); if(mid < R) update(right_son, mid+1, dr, L, R, V); } int query(int node, int st, int dr, int pos) { if(st == dr) return lazy[node]; propag(node); if(pos <= mid) return query(left_son, st, mid, pos); else return query(right_son, mid+1, dr, pos); } } aint; void add_point(int l, int r, int id) { aint.update(1, 0, h.size()-1, l, r, id); } int find_point(int x) { return aint.query(1, 0, h.size()-1, x); } void find_graph(int Start, int Finish) { int m = y.size(), n = h.size(); vector<int> s(m); iota(s.begin(), s.end(), 0); sort(s.begin(), s.end(), cmp_skywalks); reverse(s.begin(), s.end()); vector<Pair> points; aint.init(); points.push_back({Start, m}); points.push_back({Finish, m+1}); y.push_back(0); y.push_back(0); add_point(Start, Start, m); add_point(Finish, Finish, m+1); m+=2; for(auto it : s) { points.push_back({ l[it], it }); points.push_back({ r[it], it }); int p1, p2; p1 = find_point(l[it]); p2 = find_point(r[it]); if(p1 != -1) points.push_back({ l[it], p1 }); if(p2 != -1) points.push_back({ r[it], p2 }); add_point(l[it], r[it], it); } vector<vector<Pair>> vx(n), vy(m); nr = 0; for(auto p : points) { ++nr; vx[p.first].push_back({y[p.second], nr}); vy[p.second].push_back({x[p.first], nr}); } int i, j; for(i=0; i<n; ++i) { sort(vx[i].begin(), vx[i].end()); for(j=0; j+1<vx[i].size(); ++j) add_edge(vx[i][j].second, vx[i][j+1].second, vx[i][j+1].first - vx[i][j].first); } for(i=0; i<m; ++i) { sort(vy[i].begin(), vy[i].end()); for(j=0; j+1<vy[i].size(); ++j) add_edge(vy[i][j].second, vy[i][j+1].second, vy[i][j+1].first - vy[i][j].first); } } ll dijkstra(int S, int F) { priority_queue< pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>> > heap; vector<ll> d(nr+1, LLONG_MAX); d[S] = 0; heap.push({0, S}); while(heap.size()) { int node; ll dist; tie(dist, node) = heap.top(); heap.pop(); if(dist != d[node]) continue; if(node == F) return d[F]; for(auto it : v[node]) if(d[it.first] > d[node] + it.second) { d[it.first] = d[node] + it.second; heap.push({d[it.first], it.first}); } } return -1; } ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int Start, int Finish) { x = X; h = H; l = L; r = R; y = Y; adjust(Start); adjust(Finish); find_graph(Start, Finish); return dijkstra(1, 2); }

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

walk.cpp: In function 'void adjust(int)':
walk.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(id1 < pref.size() && h[pref[id1]] >= y[it])
               ~~~~^~~~~~~~~~~~~
walk.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(id2 < suff.size() && h[suff[id2]] >= y[it])
               ~~~~^~~~~~~~~~~~~
walk.cpp: In function 'void find_graph(int, int)':
walk.cpp:196:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j+1<vx[i].size(); ++j)
                  ~~~^~~~~~~~~~~~~
walk.cpp:203:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j+1<vy[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...