Submission #1080982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080982		anton	Text editor (CEOI24_editor)	C++17	14 / 100	328 ms	1180 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

int N;
vector<int> l;
vector<pii> get_adj(pii pos){
    int line = pos.first;
    vector<pii> res;
    if(pos.second == l[line]-1){
        if(pos.first<N-1){
            res.push_back({line+1, 0});
        }  
    }
    else{
        res.push_back({line, pos.second+1});
    }
    if(pos.second == 0){
        if(pos.first>0){
            res.push_back({line-1, l[line-1]-1});
        }
    }
    else{
        res.push_back({line, pos.second-1});
    }

    if(pos.first<N-1){
        res.push_back({pos.first+1, min(l[pos.first+1]-1, pos.second)});
    }
    if(pos.first>0){
        res.push_back({pos.first-1, min(l[pos.first-1]-1, pos.second)});
    }
    return res;
}

int BFS(pii begin, pii dest){
    deque<pair<int, pii>> q;
    q.push_back({0, begin});
    vector<vector<bool>> vis(N, vector<bool>(5005));
    while(q.size()>0){
        auto cur= q.front();
        q.pop_front();
        if(cur.second == dest){
            return cur.first;
        }
        else{
            for(auto e: get_adj(cur.second)){
                if(!vis[e.first][e.second]){
                    q.push_back({cur.first+1, e});
                    vis[e.first][e.second] = true;
                }
            }
        }
    }
}
signed main(){
    cin>>N;
    l.resize(N);

    pii begin;
    pii dest;
    cin>>begin.first>>begin.second;
    cin>>dest.first>>dest.second;
    begin.first--;
    begin.second--;
    dest.first--;
    dest.second--;
    for(int i = 0; i<N; i++){
        cin>>l[i];
        l[i]++;
    }

    cout<<BFS(begin, dest)<<endl;    
}

Compilation message (stderr)

Main.cpp: In function 'long long int BFS(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
Main.cpp:39:27: warning: control reaches end of non-void function [-Wreturn-type]
   39 |     deque<pair<int, pii>> q;
      |                           ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44