Submission #1227266

#TimeUsernameProblemLanguageResultExecution timeMemory
1227266pravcoderText editor (CEOI24_editor)C++20
14 / 100
426 ms20736 KiB
#include <bits/stdc++.h> #include <iostream> #include <queue> using namespace std; #define pb push_back #define mp make_pair #define rept(i, a, b) for (int i = a; i < b; i++) #define rep(i, n) for (int i = 0; i < n; i++) #define vec vector #define all(x) (x).begin(), (x).end() #define fir first #define sec second #define pq priority_queue typedef long long ll; typedef vec<int> vi; typedef vec<vi> v2i; typedef pair<int, int> pi; typedef vec<pi> vpi; typedef vec<bool> vb; typedef vec<vec<bool>> v2b; int n; vi l; pq<pair<int, pi>> q; v2i dist; v2b proc; int maxd; pi left(pi x) { if (x.second == 0) return {x.first-1, l[x.first-1]-1}; return {x.first, x.second-1}; } pi right(pi x) { if (x.second == l[x.first]-1) return {x.first+1, 0}; return {x.first, x.second+1}; } pi up(pi x) { return {x.first-1, min(x.second, l[x.first-1]-1)}; } pi down(pi x) { return {x.first+1, min(x.second, l[x.first+1]-1)}; } void print(v2i &dist, pi e) { int i = 0; for (auto a : dist) { int j = 0; for (auto x : a) { if (e.first == i && e.second == j) { if (x < 10) cout << " " << x << "!"; else if (x == maxd) cout << "--!"; else cout << x << "!"; } else { if (x < 10) cout << " " << x << " "; else if (x == maxd) cout << "-- "; else cout << x << " "; } j++; } i++; cout << "\n"; } cout << "\n"; } void add(pi x, int d) { //cout << "adding " << x.fir << " " << x.sec << endl; d++; if (dist[x.fir][x.sec] > d) { dist[x.fir][x.sec] = d; q.push({-d, {x.fir, x.sec}}); //cout << "added " << x.fir << " " << x.sec << " with dist=" << d << endl; } } int s1(pi s, pi e) { vi l(2); for (auto &x : l) cin >> x,x++; if (e.fir == 0) return 1; if (s.fir == 0) return min(e.sec+1, l[0]-e.sec+1); return min(abs(s.fir - e.sec), 2+e.sec); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); pi s; pi e; cin >> n; cin >> s.fir >> s.sec; cin >> e.fir >> e.sec; s.fir--;s.sec--;e.fir--;e.sec--; if (n==2) { cout << s1(s, e) << "\n"; return 0; } maxd = (s.sec + e.sec + abs(s.fir - e.fir)); l.resize(n); dist.resize(n, vi()); proc.resize(n, vb()); rep(i, n) { cin >> l[i]; l[i]++; dist[i].resize(l[i],maxd); proc[i].resize(l[i],false); } dist[s.fir][s.sec] = 0; q.push({0,s}); while (!proc[e.fir][e.sec] && !q.empty()) { auto v = q.top().sec; q.pop(); if (!proc[v.fir][v.sec]) { proc[v.fir][v.sec] = true; int d = dist[v.fir][v.sec]; //cout << "processing " << v.fir << " " << v.sec << " with dist=" << d << endl; if (v.fir + v.sec > 0) add(left(v), d); if (v.fir < n-1) { add(right(v), d); add(down(v), d); } if (v.fir > 0) add(up(v), d); //cout << "distance array:\n"; //print(dist, e); } } cout << dist[e.fir][e.sec] << "\n"; return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...