Submission #483496

#TimeUsernameProblemLanguageResultExecution timeMemory
483496blueSky Walking (IOI19_walk)C++17
10 / 100
4112 ms281124 KiB
#include "walk.h" #include <vector> #include <set> #include <iostream> #include <algorithm> #include <cassert> using namespace std; int N; vector<int> X; vector<int> H; int M; vector<int> L; vector<int> R; vector<int> Y; int S; int G; int ht(int i) { if(i > 0) return H[i-1]; else return Y[-i-1]; } bool cmp(int i, int j) { if(ht(i) == ht(j)) return i > j; else return ht(i) > ht(j); } vector<int> newL, newR, newY; const int mx = 4'000'000; const long long INF = 1'000'000'000'000'000'000LL; vector<int> edge[mx]; vector<long long> wt[mx]; void add_edge(int u, int v, long long w) { cerr << "add edge " << u << ' ' << v << ' ' << w << '\n'; edge[u].push_back(v); wt[u].push_back(w); edge[v].push_back(u); wt[v].push_back(w); } vector<long long> distS(mx, INF); struct distcomp { int i; }; bool operator < (distcomp A, distcomp B) { if(distS[A.i] == distS[B.i]) return A.i < B.i; return distS[A.i] < distS[B.i]; } set<pair<int, int> > points; //stored by building index + y coordinate struct loc { int b; int y; int ind; }; bool operator < (loc A, loc B) { if(A.y == B.y) return A.b < B.b; else return A.y < B.y; } long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) { N = int(x.size()); X = x; H = h; M = int(l.size()); L = l; R = r; Y = y; S = s; G = g; vector<int> obj; for(int i = 0; i < N; i++) obj.push_back(i+1); for(int j = 0; j < M; j++) obj.push_back(-(j+1)); sort(obj.begin(), obj.end(), cmp); vector<int> walk_buildings[M]; set<int> buildings; for(int o: obj) { if(o > 0) { buildings.insert(o-1); } else { int w = -o-1; set<int> endpoints; endpoints.insert(L[w]); endpoints.insert(R[w]); points.insert(make_pair(L[w], Y[w])); cerr << "inserting point A " << L[w] << ' ' << Y[w] << '\n'; points.insert(make_pair(R[w], Y[w])); cerr << "inserting point B " << R[w] << ' ' << Y[w] << '\n'; walk_buildings[w].push_back(L[w]); walk_buildings[w].push_back(R[w]); for(int z: {s, g}) { auto f = buildings.lower_bound(z); if(f != buildings.end()) if(L[w] < *f && *f < R[w]) { points.insert(make_pair(*f, Y[w])); cerr << "inserting point C " << *f << ' ' << Y[w] << '\n'; walk_buildings[w].push_back(*f); } // endpoints.insert(*f); if(f != buildings.begin()) { f--; if(L[w] < *f && *f < R[w]) { points.insert(make_pair(*f, Y[w])); cerr << "inserting point D " << *f << ' ' << Y[w] << '\n'; walk_buildings[w].push_back(*f); } } } } } vector<int> ep[N]; for(int j = 0; j < M; j++) { walk_buildings[j].erase(unique(walk_buildings[j].begin(), walk_buildings[j].end()), walk_buildings[j].end()); for(int i: walk_buildings[j]) ep[i].push_back(j); } points.insert(make_pair(S, 0)); points.insert(make_pair(G, 0)); vector<int> left_ep[N], right_ep[N]; for(int j = 0; j < M; j++) { left_ep[L[j]].push_back(j); right_ep[R[j]].push_back(j); } set< pair<int, int> > curr_walks; for(int i = 0; i < N; i++) { for(int w: left_ep[i]) { curr_walks.insert(make_pair(Y[w], w)); } for(int w: ep[i]) { auto f = curr_walks.find(make_pair(Y[w], w)); assert(f != curr_walks.end()); auto f1 = f; if(f != curr_walks.begin()) { f--; if(L[f->second] <= i && i <= R[f->second] && Y[f->second] <= H[i]) points.insert(make_pair(i, f->first)); // cerr << "inserting point " << *f << ' ' << Y[w] << '\n'; } if(f1 != curr_walks.end()) { f1++; if(f1 != curr_walks.end()) if(L[f1->second] <= i && i <= R[f1->second] && Y[f1->second] <= H[i]) points.insert(make_pair(i, f1->first)); } } for(int w: right_ep[i]) { curr_walks.erase(make_pair(Y[w], w)); } } cerr << "all points: "; for(auto p:points) cerr << p.first << ' ' << p.second << '\n'; vector<loc> places; int ct = -1; for(auto p: points) { ct++; places.push_back(loc{p.first, p.second, ct}); } sort(places.begin(), places.end(), [] (loc k, loc l) { if(k.b == l.b) return k.y < l.y; else return k.b < l.b; }); cerr << "vertical edges: \n"; for(int i = 0; i+1 < int(places.size()); i++) { if(places[i].b == places[i+1].b) add_edge(places[i].ind, places[i+1].ind, places[i+1].y - places[i].y); } sort(places.begin(), places.end(), [] (loc k, loc l) { if(k.y == l.y) return k.b < l.b; else return k.y < l.y; }); cerr << "horiz edges: \n"; cerr << "\n\n\n\nsorted places: \n"; for(auto q: places) cerr << q.b << ' ' << q.y << ' ' << q.ind << '\n'; cerr << "\n\n\n"; for(int j = 0; j < M; j++) { cerr << "j = " << j << '\n'; auto f = lower_bound(places.begin(), places.end(), loc{L[j], Y[j], -1}); auto g = f; g++; int ite = 0; while(1) { cerr << "ite = " << ite << '\n'; ite++; cerr << int(g == places.end()) << '\n'; if(g == places.end()) break; if(g->b > R[j]) break; if(g->y != Y[j]) break; // cerr << "gb = " << g->b << ", fb = " << f->b << '\n'; cerr << "g = " << g->b << ' ' << g->y << ", " << "f = " << f->b << ' ' << f->y << '\n'; add_edge(f->ind, g->ind, X[g->b] - X[f->b]); f++; g++; cerr << "done\n"; } } cerr << "j done\n"; int S_loc, G_loc; for(int i = 0; i <= ct; i++) { if(places[i].b == S && places[i].y == 0) S_loc = places[i].ind; else if(places[i].b == G && places[i].y == 0) G_loc = places[i].ind; } for(int i = 0; i <= ct; i++) cerr << "position " << places[i].b << ' ' << places[i].y << " = index " << places[i].ind << '\n'; distS[S_loc] = 0; set<distcomp> tbv; for(int i = 0; i <= ct; i++) tbv.insert(distcomp{i}); cerr << "hello\n"; while(!tbv.empty()) { int u = tbv.begin()->i; tbv.erase(tbv.begin()); cerr << "u = " << u << ", distS = " << distS[u] << '\n'; for(int e = 0; e < int(edge[u].size()); e++) { int v = edge[u][e]; long long w = wt[u][e]; if(distS[v] <= distS[u] + w) continue; tbv.erase(distcomp{v}); distS[v] = distS[u] + w; tbv.insert(distcomp{v}); } } if(distS[G_loc] >= INF) distS[G_loc] = -1; return distS[G_loc]; }

Compilation message (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:304:13: warning: 'S_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  304 |  distS[S_loc] = 0;
      |             ^
walk.cpp:332:16: warning: 'G_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  332 |  if(distS[G_loc] >= INF)
      |                ^
#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...