Submission #199217

#	Time	Username	Problem	Language	Result	Execution time	Memory
199217		Alexa2001	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1095 ms	40032 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;

map< pair<int,int>, int> dist;
queue< pair<int,int> > q;


void baga(int x, int curr)
{
    reached[x] = 1;
    for(auto it : v[x])
        {
            dist[{x, it}] = curr + 1;
            q.push({x, it});
        }
}

int solve()
{
    if(pos[0] == pos[1]) return 0;

    baga(pos[0], 0);

    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 == pos[1]) return curr;
            if(!reached[x+s]) baga(x+s, curr);
        }

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

            if(x - s == pos[1]) return curr;
            if(!reached[x-s]) baga(x-s, curr);
        }
    }

    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: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43