Submission #846897

#	Time	Username	Problem	Language	Result	Execution time	Memory
846897		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	882 ms	3800 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;
// 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 b, p, i = 0; i < m; ++i)
    {
        cin >> b >> p;
        jump[b].eb(p);
        doge[i] = {b, p};
    }
    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[doge[0].fi] = 0;
    q.emplace(0, doge[0].fi);
    while(q.size())
    {
        auto [dist, cur_sky] = q.top();
        q.pop();
        if (dist > d[cur_sky]) continue;
        if (cur_sky == doge[1].fi)
        {
            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