Submission #1222391

#TimeUsernameProblemLanguageResultExecution timeMemory
1222391jakeob77Text editor (CEOI24_editor)C++17
0 / 100
2 ms1092 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ins insert #define pb push_back #define piii pair<int,pair<int,int>> #define pii pair<int,int> void solve(){ int n;cin>>n; int st,stt,g,gg;cin>>st>>stt>>g>>gg; vector<int>a(n); for(int &d:a) cin>>d; vector<vector<vector<pii>>>adj(n+1,vector<vector<pii>>(5003)); for(int i=1;i<=n;i++){ for(int j=1;j<=a[i-1]+1;j++){ if(i!=1&&j==1){ adj[i][j].pb({i-1,a[i-2]+1}); } if(i!=n&&j==a[i-1]+1){ adj[i][j].pb({i+1,1}); } if(j!=1){ adj[i][j].pb({i,j-1}); } if(j!=a[i-1]+1){ adj[i][j].pb({i,j+1}); } if(i!=1){ adj[i][j].pb({i-1,j}); } if(i!=n){ adj[i][j].pb({i+1,j}); } } }/* for(int i=1;i<=n;i++){ for(int j=1;j<=a[i-1]+1;j++){ for(auto el:adj[i][j]){ cout<<el.first<<'/'<<el.second<<' '; } cout<<endl; } cout<<endl; } */ vector<vector<int>>dist(n+1,vector<int>(5003,int(1e9+2e6))); priority_queue<piii,vector<piii>,greater<piii>>pq; pq.push({0,{st,stt}}); while(pq.size()){ auto [d,p]=pq.top();pq.pop(); //cout<<p.first<<'/'<<p.second<<endl; if(d>=dist[p.first][p.second]) continue; dist[p.first][p.second]=d; if(p.first==g&&p.second==gg) break; for(auto ne:adj[p.first][p.second]){ if(d+1<dist[ne.first][ne.second]){ //cout<<"next:"<<ne.first<<' '<<ne.second<<' '<<d<<endl; pq.push({d+1,{ne.first,ne.second}}); } } } cout<<dist[g][gg]<<endl; } int main() { int t=1; while(t--)solve(); }
#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...