Submission #199223

#	Time	Username	Problem	Language	Result	Execution time	Memory
199223		Alexa2001	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1098 ms	102756 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

/// 12:08

const int Nmax = 30005;
const int base = 30007;

vector<int> v[Nmax];

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

int n, m;

unordered_map<int, int> dist;
queue< int > q;


static int code(int x, int y)
{
    return x * base + y;
}

static pair<int,int> decode(int x)
{
    return {x / base, x % base};
}

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

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

    baga(pos[0], 0);

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

        int curr = dist[code(x, s)];

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

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

        if(x - s >= 0 && !dist[code(x - s, s)])
        {
            dist[code(x - s, s)] = curr + 1;
            q.push(code(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]);
    }

    for(i=0; i<n; ++i)
    {
        sort(v[i].begin(), v[i].end());
        v[i].erase( unique(v[i].begin(), v[i].end()) , v[i].end() );
    }

    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