Submission #199214

#	Time	Username	Problem	Language	Result	Execution time	Memory
199214		Alexa2001	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	6 ms	1144 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

/// 12:08

const int Nmax = 30005;

vector<int> v[Nmax];

int salt[Nmax], pos[Nmax];
bool reached[Nmax];

int n, m;

int solve()
{
    map< pair<int,int>, int> dist;
    queue< pair<int,int> > q;

    q.push({pos[0], salt[0]});
    dist[ {pos[0], salt[0]} ] = 1;

    while(q.size())
    {
        int x, s;
        tie(x, s) = q.front();
        q.pop();

        int curr = dist[{ x, s }];

        if(x + s < n && !dist[{ x + s, s }])
        {
            dist[{ x + s, s }] = curr + 1;
            q.push({x+s, s});
        }

        if(x - s >= 0 && !dist[{ x - s, s }])
        {
            dist[{ x - s, s }] = curr + 1;
            q.push({x-s, s});
        }


        if(!reached[x])
        {
            reached[x] = 1;
            if(x == pos[1]) return curr - 1;

            for(auto it : v[x])
                if(!dist[{ x, it }])
                {
                    dist[{ x, it }] = curr;
                    q.push({x, it});
                }
        }
    }

    return -1;
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    int i;
    for(i=0; i<m; ++i)
    {
        cin >> pos[i] >> salt[i];
        v[pos[i]].push_back(salt[i]);
    }

    cout << solve() << '\n';

    return 0;
}

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