Submission #846896

#	Time	Username	Problem	Language	Result	Execution time	Memory
846896		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	856 ms	6104 KiB

skyscraper

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 3e5 + 2;
int n, m, b[nmax], p[nmax];
int mx = 0;
bool checksub123()
{
    return (n <= 2000 && m <= 2000 && mx <= 2000);
}
void sub123()
{
    vector <vector <int>> pos(n);
    vector <pii> doge(m);
    for (int i = 0; i < m; ++i)
    {
        pos[b[i]].eb(i);
        doge[i] = {b[i], p[i]};
    }
    vector <int> d(m, 1e9); //dijkstra theo dog 0 -> m-1
    priority_queue <pii, vector <pii>, greater <pii>> q;
    d[0] = 0;
    q.emplace(0, 0);
    while(q.size())
    {
        auto [dist, u] = q.top();
        q.pop();
        if (dist > d[u]) continue;
        if (u == 1)
        {
            cout << dist;
            exit(0);
        }
        auto [B, P] = doge[u];
        for (int i = 0; i <= n / P; ++i)
        {
            int left = B - i * P;
            int right = B + i * P;
            if (left >= 0)
            {
                for (auto &j : pos[left])
                    if (d[j] > dist + i)
                        q.emplace(d[j] = dist + i, j);
            }
            if (right < n)
            {
                for (auto &j : pos[right])
                    if (d[j] > dist + i)
                        q.emplace(d[j] = dist + i, j);
            }
            
        }
    }
    cout << -1;
    exit(0);
}
void sub45()
{
    vector <vector <int>> jump(n);
    vector <pii> doge(m);
    for (int i = 0; i < m; ++i)
    {
        jump[b[i]].eb(p[i]);
        doge[i] = {b[i], p[i]};
    }
    vector <int> d(n, 1e9); //dp theo skyscraper tu 0 -> n - 1
    priority_queue <pii, vector <pii>, greater <pii>> q;
    vector <bool> vs(n, 0);
    d[b[0]] = 0;
    q.emplace(0, b[0]);
    while(q.size())
    {
        auto [dist, cur_sky] = q.top();
        q.pop();
        if (dist > d[cur_sky]) continue;
        if (cur_sky == b[1])
        {
            cout << dist;
            exit(0);
        }
        if (jump[cur_sky].empty()) continue;
        if (vs[cur_sky]) continue;
        vs[cur_sky] = 1;
        for (auto &P : jump[cur_sky])
        {
            for (int i = 1; cur_sky + i * P < n; ++i)
            {
                int right = cur_sky + i * P;
                if (d[right] > dist + i)
                    q.emplace(d[right] = dist + i, right);
            }
            for (int i = 1; cur_sky - i * P >= 0; ++i)
            {
                int left = cur_sky - i * P;
                if (d[left] > dist + i)
                    q.emplace(d[left] = dist + i, left);
            }
        }
    }
    cout << -1;
    exit(0);
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
        cin >> b[i] >> p[i], mx = max(mx, p[i]);
    if (checksub123()) sub123();
    sub45();
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:9:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:116:31: note: in expansion of macro 'nx'
  116 |     if (ifstream(task".inp")) nx
      |                               ^~
skyscraper.cpp:9:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:116:31: note: in expansion of macro 'nx'
  116 |     if (ifstream(task".inp")) nx
      |                               ^~

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