oj.uz

답안 #1080979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1080979 2024-08-29T16:36:26 Z anton Text editor (CEOI24_editor) C++17
0 / 100
 4000 ms 378504 KB 
#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});
    set<pii> vis;
    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.find(e)==vis.end()){
                    q.push_back({cur.first+1, e});
                    vis.insert(e);
                }
            }
        }
    }
}
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

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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 4086 ms 378504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 61 ms 5992 KB Output is correct
5 Correct 128 ms 9552 KB Output is correct
6 Correct 10 ms 1624 KB Output is correct
7 Correct 294 ms 22688 KB Output is correct
8 Execution timed out 4066 ms 220332 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Execution timed out 4086 ms 378504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 4086 ms 378504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Execution timed out 4086 ms 378504 KB Time limit exceeded
5 Halted 0 ms 0 KB -