oj.uz

Submission #956222

# Submission time Handle Problem Language Result Execution time Memory
956222 2024-04-01T10:55:51 Z Nelt Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 492 ms 31528 KB 
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
 
void solve()
{
    ll n, m;
    cin >> n >> m;
    ll b[m], p[m];
    vector<ll> eq[n];
    for (ll i = 0; i < m; i++)
        cin >> b[i] >> p[i], eq[b[i]].push_back(p[i]);
    map<ll, ll> dist[n];
    dist[b[0]][p[0]] = 0;
    queue<pair<ll, ll>> q;
    q.push(make_pair(b[0], p[0]));
    while (!q.empty())
    {
        auto [i, j] = q.front();
        q.pop();
        if (i == b[1])
        {
            cout << dist[i][j] << endl;
            return;
        }
        if (i - j >= 0 and !dist[i - j].count(j) and dist[i - j].size() <= 500)
            dist[i - j][j] = dist[i][j] + 1, q.push(make_pair(i - j, j));
        if (i + j < n and !dist[i + j].count(j) and dist[i + j].size() <= 500)
            dist[i + j][j] = dist[i][j] + 1, q.push(make_pair(i + j, j));
        for (ll k : eq[i])
        {
            if (i - k >= 0 and !dist[i - k].count(k) and dist[i - k].size() <= 500)
                dist[i - k][k] = dist[i][j] + 1, q.push(make_pair(i - k, k));
            if (i + k < n and !dist[i + k].count(k) and dist[i + k].size() <= 500)
                dist[i + k][k] = dist[i][j] + 1, q.push(make_pair(i + k, k));
        }
        if (!dist[b[1]].empty())
        {
            ll ans = 1e18;
            for (auto j : dist[b[1]])
                ans = min(ans, j.second);
            cout << ans << endl;
            return;
        }
    }
    cout << "-1\n";
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 4 ms 856 KB Output is correct
15 Correct 1 ms 516 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 4 ms 1628 KB Output is correct
29 Correct 12 ms 4188 KB Output is correct
30 Correct 3 ms 1592 KB Output is correct
31 Correct 7 ms 2652 KB Output is correct
32 Correct 4 ms 1884 KB Output is correct
33 Correct 36 ms 8060 KB Output is correct
34 Correct 16 ms 4444 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 488 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 4 ms 860 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 4 ms 1628 KB Output is correct
29 Correct 12 ms 4188 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 6 ms 2652 KB Output is correct
32 Correct 4 ms 1884 KB Output is correct
33 Correct 32 ms 8000 KB Output is correct
34 Correct 19 ms 4444 KB Output is correct
35 Correct 6 ms 1884 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 3 ms 1112 KB Output is correct
38 Correct 5 ms 1628 KB Output is correct
39 Correct 7 ms 1368 KB Output is correct
40 Correct 4 ms 1368 KB Output is correct
41 Correct 5 ms 1372 KB Output is correct
42 Correct 3 ms 1372 KB Output is correct
43 Correct 4 ms 1500 KB Output is correct
44 Correct 4 ms 1284 KB Output is correct
45 Correct 468 ms 31364 KB Output is correct
46 Correct 307 ms 16976 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 2 ms 940 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 4 ms 1628 KB Output is correct
29 Correct 12 ms 4188 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 6 ms 2440 KB Output is correct
32 Correct 4 ms 1884 KB Output is correct
33 Correct 32 ms 8020 KB Output is correct
34 Correct 17 ms 4440 KB Output is correct
35 Correct 8 ms 1884 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 4 ms 1116 KB Output is correct
38 Correct 8 ms 1628 KB Output is correct
39 Correct 4 ms 1372 KB Output is correct
40 Correct 5 ms 1360 KB Output is correct
41 Correct 5 ms 1372 KB Output is correct
42 Correct 4 ms 1372 KB Output is correct
43 Correct 4 ms 1500 KB Output is correct
44 Correct 4 ms 1284 KB Output is correct
45 Correct 492 ms 31528 KB Output is correct
46 Correct 289 ms 16896 KB Output is correct
47 Correct 5 ms 2392 KB Output is correct
48 Correct 6 ms 2908 KB Output is correct
49 Correct 5 ms 2908 KB Output is correct
50 Correct 4 ms 2908 KB Output is correct
51 Correct 14 ms 5980 KB Output is correct
52 Correct 14 ms 6492 KB Output is correct
53 Correct 8 ms 3980 KB Output is correct
54 Correct 3 ms 3420 KB Output is correct
55 Correct 3 ms 3932 KB Output is correct
56 Correct 8 ms 5840 KB Output is correct
57 Correct 2 ms 2652 KB Output is correct
58 Correct 14 ms 7392 KB Output is correct
59 Correct 9 ms 6880 KB Output is correct
60 Correct 9 ms 6680 KB Output is correct
61 Correct 10 ms 6560 KB Output is correct
62 Incorrect 10 ms 4188 KB Output isn't correct
63 Halted 0 ms 0 KB -