Submission #1244068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244068		pumkinhead	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1097 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int SQRT = 1.7e2;
struct BfsElem{
    int node, dir, dist;  
};
int solve(int n, int m, vector<vector<int>> doges, int targetBuilding){
    vector<vector<bool>> visited(n, vector<bool>(SQRT, false));
    queue<BfsElem> bfs;
    bfs.push({0, 0, 0});
    int ans = -1;
    int mults[2] = {1, -1};
    while(bfs.size()){
        BfsElem elem = bfs.front();
        bfs.pop();
        if(elem.node < 0 || n <= elem.node) continue;
        if(elem.node == targetBuilding){
            ans = elem.dist;
            break;
        }
        if(abs(elem.dir) < SQRT){
            if(visited[elem.node][abs(elem.dir)]) continue;
            visited[elem.node][abs(elem.dir)] = true;
        }
        while(doges[elem.node].size()){
            for(int mult : mults){
                int newDir = mult * doges[elem.node].back();
                bfs.push({elem.node + newDir, newDir, elem.dist + 1});
            }
            doges[elem.node].pop_back();
        }
        if(elem.dir != 0){
            bfs.push({elem.node + elem.dir, elem.dir, elem.dist + 1});
        }
    }
    return ans;
}
int solve2(int n, int m, vector<vector<int>> doges, int targetBuilding){
    // vector<vector<bool>> visited(n, vector<bool>(n, false));
    // auto comp = [](const BfsElem& left, const BfsElem& right){
    //     left.dist > right.dist;
    // };
    // priority_queue<BfsElem, vector<BfsElem>, decltype(comp)> bfs(comp);
    queue<BfsElem> bfs;
    bfs.push({0, 0, 0});
    int ans = -1;
    int mults[2] = {1, -1};
    while(bfs.size()){
        BfsElem elem = bfs.front();
        bfs.pop();
        if(elem.node < 0 || n <= elem.node) continue;
        if(elem.node == targetBuilding){
            ans = elem.dist;
            break;
        }
        // if(abs(elem.dir) < visited[elem.node].size()){
        //     if(visited[elem.node][abs(elem.dir)]) continue;
        //     visited[elem.node][abs(elem.dir)] = true;
        // }
        while(doges[elem.node].size()){
            for(int mult : mults){
                int newDir = mult * doges[elem.node].back();
                bfs.push({elem.node + newDir, newDir, elem.dist + 1});
            }
            doges[elem.node].pop_back();
        }
        bfs.push({elem.node + elem.dir, elem.dir, elem.dist + 1});
    }
    return ans;
}
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    vector<vector<int>> doges(n);
    int targetBuilding;
    for(int i=0; i<m; i++){
        int b, p;
        cin>>b>>p;
        if(i == 1){
            targetBuilding = b;
        }
        doges[b].push_back(p);
    }
    int ans = solve2(n, m, doges, targetBuilding);
    cout<<ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43