oj.uz

Submission #846887

# Submission time Handle Problem Language Result Execution time Memory
846887 2023-09-08T15:28:03 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 5348 KB 
#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 doge 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); //dijkstra theo skyscraper tu 0 -> n - 1
    priority_queue <pii, vector <pii>, greater <pii>> q;
    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;
        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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 8 ms 2396 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 25 ms 2652 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2392 KB Output is correct
24 Correct 1 ms 2648 KB Output is correct
25 Correct 1 ms 2648 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2648 KB Output is correct
29 Correct 1 ms 2408 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2644 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 2 ms 2652 KB Output is correct
34 Correct 2 ms 2652 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2424 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 7 ms 2396 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2512 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2392 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 2 ms 2648 KB Output is correct
34 Correct 2 ms 2652 KB Output is correct
35 Correct 5 ms 3040 KB Output is correct
36 Correct 1 ms 2648 KB Output is correct
37 Correct 4 ms 2908 KB Output is correct
38 Correct 5 ms 3160 KB Output is correct
39 Correct 4 ms 3160 KB Output is correct
40 Correct 5 ms 3160 KB Output is correct
41 Correct 5 ms 3164 KB Output is correct
42 Correct 4 ms 3028 KB Output is correct
43 Correct 5 ms 3160 KB Output is correct
44 Correct 63 ms 3164 KB Output is correct
45 Correct 5 ms 3164 KB Output is correct
46 Correct 5 ms 3164 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2512 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 7 ms 2396 KB Output is correct
14 Correct 2 ms 2676 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 24 ms 2684 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2572 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 2 ms 2648 KB Output is correct
34 Correct 2 ms 2652 KB Output is correct
35 Correct 4 ms 2908 KB Output is correct
36 Correct 1 ms 2652 KB Output is correct
37 Correct 4 ms 2912 KB Output is correct
38 Correct 5 ms 3252 KB Output is correct
39 Correct 4 ms 3168 KB Output is correct
40 Correct 5 ms 3168 KB Output is correct
41 Correct 4 ms 3192 KB Output is correct
42 Correct 4 ms 3168 KB Output is correct
43 Correct 4 ms 3160 KB Output is correct
44 Correct 68 ms 3140 KB Output is correct
45 Correct 5 ms 3160 KB Output is correct
46 Correct 5 ms 3164 KB Output is correct
47 Correct 7 ms 3960 KB Output is correct
48 Correct 4 ms 3676 KB Output is correct
49 Correct 4 ms 3676 KB Output is correct
50 Correct 3 ms 3676 KB Output is correct
51 Correct 11 ms 5348 KB Output is correct
52 Correct 13 ms 4824 KB Output is correct
53 Correct 6 ms 4696 KB Output is correct
54 Correct 2 ms 3420 KB Output is correct
55 Correct 2 ms 3420 KB Output is correct
56 Correct 947 ms 4984 KB Output is correct
57 Correct 2 ms 4052 KB Output is correct
58 Execution timed out 1027 ms 4048 KB Time limit exceeded
59 Halted 0 ms 0 KB -