Submission #625089

#	Time	Username	Problem	Language	Result	Execution time	Memory
625089		Hanksburger	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1075 ms	56856 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
queue<pair<pair<int, int>, int> > q;
map<pair<int, int>, bool> mp;
int a[30005], b[30005];
vector<int> v[30005];
bool visited[30005];
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];
        v[a[i]].push_back(b[i]);
    }
    for (int i=0; i<m; i++)
        if (a[i]==a[0])
            q.push({{a[i], b[i]}, 0});
    while (!q.empty())
    {
        int x=q.front().first.first, y=q.front().first.second, z=q.front().second;
        q.pop();
        if (x==a[1])
        {
            cout << z;
            return 0;
        }
        for (int u=x-y; u<=x+y; u+=y*2)
        {
            if (u<0 || u>=n)
                continue;
            if (!visited[u])
            {
                for (int i=0; i<v[u].size(); i++)
                {
                    q.push({{u, v[u][i]}, z+1});
                    mp[{u, v[u][i]}]=1;
                }
                visited[u]=1;
            }
            if (!mp[{u, y}])
            {
                q.push({{u, y}, z+1});
                mp[{u, y}]=1;
            }
        }
    }
    cout << -1;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 for (int i=0; i<v[u].size(); i++)
      |                               ~^~~~~~~~~~~~

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