제출 #1312684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312684		paulllol	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1095 ms	2408 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,e,f,g,ans;
bool c,d,vs[30001];
vector<pair<int,int>> v[30001];
queue<tuple<int,int,bool,bool,int>> q;
int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        v[a].emplace_back(make_pair(b,i));
        if(i==0){
            e=a;
            f=b;
        }
        else if(i==1){
            ans=a;
        }
    }
    q.emplace(make_tuple(e,0,0,0,0));
    while(!q.empty()){
        a=get<0>(q.front());
        b=get<1>(q.front());
        c=get<2>(q.front());
        d=get<3>(q.front());
        g=get<4>(q.front());
        q.pop();
        if(a==ans){
            cout<<g;
            return 0;
        }
        if(c==1&&a-b>=0){
            q.emplace(make_tuple(a-b,b,1,0,g+1));
        }
        if(d==1&&a+b<n){
            q.emplace(make_tuple(a+b,b,0,1,g+1));
        }
        for(int i=0;i<v[a].size();i++){
            if(vs[v[a][i].second]==0){
                vs[v[a][i].second]=1;
                if(a-v[a][i].first>=0){
                q.emplace(make_tuple(a-v[a][i].first,v[a][i].first,1,0,g+1));
                }
                if(a+v[a][i].first<n){
                    q.emplace(make_tuple(a+v[a][i].first,v[a][i].first,0,1,g+1));
                }
            }
        }
    }
    cout<<"-1";
}

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