Submission #870359

#	Time	Username	Problem	Language	Result	Execution time	Memory
870359		Namviet2704	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	122 ms	8992 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int sqr = 205;
const int N = 4e4 + 2;

struct node
{
    int v, p, w;
    node(int v, int p, int w) : v(v), p(p), w(w) {}
};

int dis[N];
bool vs[N][sqr + 10];
vector<int> adj[N];
queue<node> q;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int s, t, n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int v, p;
        cin >> v >> p;
        adj[v].push_back(p);
        if (i == 0)
            s = v;
        if (i == 1)
            t = v;
    }
    memset(dis, -1, sizeof(dis));
    q.emplace(s, 0, 0);
    while (!q.empty())
    {
        node h = q.front();
        q.pop();
        if (h.v < 0 || h.v >= n)
            continue;
        if (abs(h.p) < sqr)
        { // neu p < can thi chi duyet qua 1 lan
            if (vs[h.v][abs(h.p)])
                continue;
            vs[h.v][abs(h.p)] = 1;
        }
        if (dis[h.v] == -1)
        {
            dis[h.v] = h.w;
            for (int p : adj[h.v])
            {
                q.emplace(h.v + p, p, h.w + 1);  // di theo buoc nhay p ve huong ben phai
                q.emplace(h.v - p, -p, h.w + 1); // di theo buoc nhay p ve huong ben trai
            }
        }
        q.emplace(h.v + h.p, h.p, h.w + 1); // tiep tuc di theo buoc nhay
    }
    cout << dis[t];
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:11:48: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   11 |     node(int v, int p, int w) : v(v), p(p), w(w) {}
      |                                                ^
skyscraper.cpp:23:9: note: 's' was declared here
   23 |     int s, t, n, m;
      |         ^
skyscraper.cpp:60:18: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     cout << dis[t];
      |                  ^

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