Submission #1230155

#TimeUsernameProblemLanguageResultExecution timeMemory
1230155kfhjadWalk (CEOI06_walk)C++20
74 / 100
1099 ms95840 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using Point = pair<int, int>; map<Point, vector<pair<Point, int>>> adj; map<Point, int> best; map<Point, Point> prevv; int dist(Point a, Point b) { return abs(a.first - b.first) + abs(a.second - b.second); } int main() { cin.tie(NULL) -> sync_with_stdio(false); int destX, destY, N; cin >> destX >> destY >> N; vector<array<int, 4>> events; for (int i = 0; i < N; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); if (x1 - 1 >= destX) continue; events.push_back({x1 - 1, y1 - 1, y2 + 1, 0}); events.push_back({x2 + 1, y1 - 1, y2 + 1, 1}); best[{x1 - 1, y1 - 1}] = 1E9; best[{x1 - 1, y2 + 1}] = 1E9; best[{x2 + 1, y1 - 1}] = 1E9; best[{x2 + 1, y2 + 1}] = 1E9; } best[{destX, destY}] = 1E9; events.push_back({0, 0, 0, 1}); events.push_back({destX, destY, destY, 0}); sort(events.begin(), events.end(), [](auto& a, auto& b) { if (a[0] == b[0]) { if (a[3] ^ b[3]) // one of them end return a[3] == 1; return a[1] < b[1]; } else return a[0] < b[0]; }); // y, x map<int, int> active; for (auto& [x, y1, y2, _] : events) { auto it = active.lower_bound(y1); while (it != active.end() && it -> first <= y2) { Point p = {it -> second, it -> first}; adj[p].push_back({{x, y1}, dist(p, {x, y1})}); adj[p].push_back({{x, y2}, dist(p, {x, y2})}); it = active.erase(it); } // connect points outside of segment it = active.upper_bound(y2); if (it != active.end()) { Point p = {it -> second, it -> first}; adj[p].push_back({{x, y2}, dist(p, {x, y2})}); } it = active.lower_bound(y1); if (it != active.begin()) { --it; Point p = {it -> second, it -> first}; adj[p].push_back({{x, y1}, dist(p, {x, y1})}); } active[y1] = x; active[y2] = x; } using T = pair<int, Point>; priority_queue<T, vector<T>, greater<T>> q; q.push({0, {0, 0}}); while (!q.empty()) { auto [d, point] = q.top(); q.pop(); for (auto& [u, w] : adj[point]) { if (d + w < best[u]) q.push({best[u] = d + w, u}), prevv[u] = point; } } vector<Point> path; Point stop = {-1, -1}; prevv[{0, 0}] = stop; Point p = {destX, destY}; while (prevv[p] != stop) { path.push_back(p); p = prevv[p]; } path.push_back({0, 0}); reverse(path.begin(), path.end()); vector<Point> ans; for (int i = 1; i < path.size(); ++i) { int dx = path[i].first - path[i - 1].first; int dy = path[i].second - path[i - 1].second; if (ans.empty()) { if (dx) ans.push_back({dx, 0}); if (dy) ans.push_back({0, dy}); continue; } if (ans.back().first == 0) { ans.back().second += dy; if (dx) ans.push_back({dx, 0}); } else { ans.back().first += dx; if (dy) ans.push_back({0, dy}); } } cout << best[{destX, destY}] << endl; cout << ans.size() << endl; for (auto [dx, dy] : ans) cout << dx << ' ' << dy << '\n'; return 0; } /*****************************= -+**********************************= :-*****************************************+: ..:*************+=+*******************************=. ..-==*****************+=-+*****************************+. ..-=***********************+--+****************************= :+**************#*#**********+--+***************************- .=--=. .+*********************#*********+--****************************++++----: -+***********************##*********--+********************************+--=. =****=**********************#*********+-=***************************#*****+--= .=****+***********************************-=*********************#*****##*****=-=. :=*****=************************************=-*****************#******#####*****=-=. .=**+***=**************************#**********==***********##*******#**######*****+-=. +***=***+***************************#**********-+*****####********#*****#####******+-=: =+**=****+****************#**********************-*####*********##***#*#######*******+-=. .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-== -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*. =*###+######+############################################=..+=-+.########%##%##%##########*-+* +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#. .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+ .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+## .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*## .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%= #%%############=###- .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+ #%%###########*=###+ :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####- .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+ %%######%#####=*####. #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%- %%######%#####=#####. -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%# #%######%####*=###%# *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%* #%######%####+*###%# *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%# +%######%####=####%#. =.=###%%%%%:.............:............#*%%####*#*=====%@%%% :%#####%%####+######: .=%##%%%%%*.............:............#*%%####+#+======%#%* .:-=%%%%%%%%###+#####+#- .%%##%%%-*-..............::::.......#+%%####+#=====-...#: :*%%%%%%%%%%%%%%%%###*#####=#= .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+ *-#%#%%- -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#* =*.%%%%= .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*# #..%%%#. -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*# +- :%%%#+ =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:. .#. =%% .*= -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+. .* *%- .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#. .=. ## ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%: ..=*- .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-. #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:. *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=: :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#: .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%: .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@- ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%: .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%:: .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-:: .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=: -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+: %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+- *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#- :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%- :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%* :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*% :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+ -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*% -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+ -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%- -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/
#Verdict Execution timeMemoryGrader output
Fetching results...