제출 #1081018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081018		anton	Text editor (CEOI24_editor)	C++17	56 / 100	4025 ms	332288 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> interesting;
vector<pair<int, pii>> get_adj(pii pos){
    int line = pos.first;
    int col = pos.second;
    vector<pair<int, pii>> res;

    for(auto e: interesting){
        if(e.first == line){
            res.push_back({abs(e.second-col), e});
        }
    }
    
    res.push_back({col, {line, 0}});
    res.push_back({l[line]-1-col, {line, l[line]-1}});
    if(line<N-1){
        res.push_back({1, {line+1, min(l[line+1]-1, col)}});
        if(col == l[line]-1){
            res.push_back({1, {line+1,0}});
        }
    }
    if(line>0){
        res.push_back({1, {line-1, min(l[line-1]-1, col)}});
        if(col == 0){
            res.push_back({1, {line-1, l[line-1]-1}});
        }
    }
    return res;
}

const int INF = 1e9;

int flat(pii a){
    return a.first* INF + a.second;
}

int BFS(pii begin, pii dest){
    priority_queue<pair<int, pii>> pq;
    pq.push({-0, begin});
    unordered_map<int, int> dist;
    dist[flat(begin)] = 0;

    while(pq.size()>0){
        auto cur= pq.top();
        cur.first*=-1;
        pq.pop();
        //cout<<cur.first<<" "<<cur.second.first<<" "<<cur.second.second<<endl;
        
        
        for(auto e: get_adj(cur.second)){
            int cost = e.first + cur.first;
            if(dist.find(flat(e.second)) == dist.end() || dist[flat(e.second)] >cost){

                pq.push({-cost, e.second});
                dist[flat(e.second)] = cost;
            }
        }
    
    }   

    return dist[flat(dest)];
}
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--;
    
    interesting.push_back(begin);
    interesting.push_back(dest);
    for(int i = 0; i<N; i++){
        cin>>l[i];
        l[i]++;
    }

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

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