oj.uz

Submission #1015692

# Submission time Handle Problem Language Result Execution time Memory
1015692 2024-07-06T16:35:59 Z andrei_iorgulescu Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 96204 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m;
int b[30005],p[30005];
map<pair<int,int>, bool> viz,luat;
map<pair<int,int>, int> d;
vector<int> what[30005];
int str,fin;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> b[i] >> p[i],what[b[i]].push_back(p[i]);
    str = b[1],fin = b[2];
    deque<pair<int,int>> q;
    q.push_back({str,0});
    viz[{str,0}] = true;
    while (!q.empty())
    {
        pair<int,int> nod = q.front();
        q.pop_front();
        if (luat[nod])
            continue;
        luat[nod] = true;
        int dist = d[nod];
        if (nod.second != 0)
        {
            pair<int,int> vec;
            vec = {nod.first,0};
            if (!viz[vec] or d[vec] > dist)
            {
                viz[vec] = true;
                q.push_front(vec);
                d[vec] = dist;
            }

            vec = {nod.first + nod.second,nod.second};
            if (!viz[vec] and vec.first >= 0 and vec.first < n)
            {
                viz[vec] = true;
                q.push_back(vec);
                d[vec] = dist + 1;
            }

            vec = {nod.first - nod.second,nod.second};
            if (!viz[vec] and vec.first >= 0 and vec.first < n)
            {
                viz[vec] = true;
                q.push_back(vec);
                d[vec] = dist + 1;
            }
        }
        else
        {
            for (auto it : what[nod.first])
            {
                pair<int,int> vec = {nod.first,it};
                if (!viz[vec] or d[vec] > dist)
                {
                    viz[vec] = true;
                    q.push_front(vec);
                    d[vec] = dist;
                }
            }
        }
    }
    if (!viz[{fin,0}])
        cout << -1;
    else
        cout << d[{fin,0}];
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 7 ms 2136 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 8 ms 2624 KB Output is correct
15 Correct 7 ms 2396 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 9 ms 2140 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 7 ms 2416 KB Output is correct
15 Correct 7 ms 2396 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 28 ms 4112 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 11 ms 2648 KB Output is correct
24 Correct 19 ms 4188 KB Output is correct
25 Correct 11 ms 3160 KB Output is correct
26 Correct 11 ms 2908 KB Output is correct
27 Correct 7 ms 2652 KB Output is correct
28 Correct 30 ms 6028 KB Output is correct
29 Correct 107 ms 12876 KB Output is correct
30 Correct 20 ms 4736 KB Output is correct
31 Correct 50 ms 7764 KB Output is correct
32 Correct 35 ms 5832 KB Output is correct
33 Correct 226 ms 24320 KB Output is correct
34 Correct 239 ms 24128 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 6 ms 2140 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 10 ms 2416 KB Output is correct
15 Correct 7 ms 2400 KB Output is correct
16 Correct 2 ms 1116 KB Output is correct
17 Correct 28 ms 4188 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1176 KB Output is correct
23 Correct 12 ms 2756 KB Output is correct
24 Correct 20 ms 3932 KB Output is correct
25 Correct 11 ms 3164 KB Output is correct
26 Correct 8 ms 2908 KB Output is correct
27 Correct 7 ms 2724 KB Output is correct
28 Correct 27 ms 5972 KB Output is correct
29 Correct 82 ms 13080 KB Output is correct
30 Correct 20 ms 4696 KB Output is correct
31 Correct 42 ms 7764 KB Output is correct
32 Correct 26 ms 5980 KB Output is correct
33 Correct 187 ms 24148 KB Output is correct
34 Correct 195 ms 24148 KB Output is correct
35 Correct 189 ms 24460 KB Output is correct
36 Correct 27 ms 5204 KB Output is correct
37 Correct 370 ms 36488 KB Output is correct
38 Correct 369 ms 35944 KB Output is correct
39 Correct 345 ms 35920 KB Output is correct
40 Correct 346 ms 36056 KB Output is correct
41 Correct 364 ms 35860 KB Output is correct
42 Correct 11 ms 3420 KB Output is correct
43 Correct 10 ms 3164 KB Output is correct
44 Correct 7 ms 2500 KB Output is correct
45 Execution timed out 1081 ms 96016 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 0 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 0 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 5 ms 2208 KB Output is correct
12 Correct 1 ms 1240 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 7 ms 2396 KB Output is correct
15 Correct 10 ms 2404 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 22 ms 4176 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 3 ms 1884 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 9 ms 2672 KB Output is correct
24 Correct 17 ms 4188 KB Output is correct
25 Correct 10 ms 3164 KB Output is correct
26 Correct 8 ms 2908 KB Output is correct
27 Correct 8 ms 2652 KB Output is correct
28 Correct 26 ms 6128 KB Output is correct
29 Correct 80 ms 12880 KB Output is correct
30 Correct 18 ms 4700 KB Output is correct
31 Correct 41 ms 7648 KB Output is correct
32 Correct 28 ms 5972 KB Output is correct
33 Correct 190 ms 24148 KB Output is correct
34 Correct 202 ms 24148 KB Output is correct
35 Correct 205 ms 24212 KB Output is correct
36 Correct 27 ms 5212 KB Output is correct
37 Correct 399 ms 36724 KB Output is correct
38 Correct 333 ms 36068 KB Output is correct
39 Correct 350 ms 36044 KB Output is correct
40 Correct 325 ms 36036 KB Output is correct
41 Correct 343 ms 36000 KB Output is correct
42 Correct 13 ms 3672 KB Output is correct
43 Correct 10 ms 3164 KB Output is correct
44 Correct 7 ms 2396 KB Output is correct
45 Execution timed out 1103 ms 96204 KB Time limit exceeded
46 Halted 0 ms 0 KB -