제출 #625081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625081		Hanksburger	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	340 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
queue<pair<pair<int, int>, int> > q;
int A[30005], B[30005], C[30005];
map<pair<int, int>, bool> mp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++)
    {
        cin >> A[i] >> B[i];
        C[A[i]]=B[i];
    }
    q.push({{A[0], B[0]}, 0});
    mp[{A[0], B[0]}]=1;
    while (!q.empty())
    {
        int a=q.front().first.first, b=q.front().first.second, c=q.front().second;
        q.pop();
        if (a==A[1])
        {
            cout << c;
            return 0;
        }
        if (a+b<n)
        {
            if (!mp[{a+b, C[a+b]}])
            {
                q.push({{a+b, C[a+b]}, c+1});
                mp[{a+b, C[a+b]}]=1;
            }
            if (!mp[{a+b, b}])
            {
                q.push({{a+b, b}, c+1});
                mp[{a+b, b}]=1;
            }
        }
        if (a-b>=0)
        {
            if (!mp[{a-b, C[a-b]}])
            {
                q.push({{a-b, C[a-b]}, c+1});
                mp[{a-b, C[a-b]}]=1;
            }
            if (!mp[{a-b, b}])
            {
                q.push({{a-b, b}, c+1});
                mp[{a-b, b}]=1;
            }
        }
    }
    cout << -1;
    return 0;
}

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