oj.uz

Submission #1015725

# Submission time Handle Problem Language Result Execution time Memory
1015725 2024-07-06T17:06:19 Z andrei_iorgulescu Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 174 ms 54076 KB 
#include <bits/stdc++.h>

using namespace std;

int hsh(pair<int,int> pr)
{
    return pr.first * 31000 + pr.second;
}

int n,m;
int b[30005],p[30005];
unordered_map<int, bool> luat;
bitset<1000000000> viz;
unordered_map<int, int> d;
vector<int> what[30005];
int str,fin;
pair<int,int> q[2000005];

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];
    int bk = 1e6,fr = 1e6;
    q[bk] = {str,0};
    viz[hsh({str,0})] = 1;
    int cate = 0,lul = 1e6;
    while (bk <= fr)
    {
        pair<int,int> nod = q[fr];
        //cout << nod.first << ' ' << nod.second << endl;
        int dehnod = hsh(nod);
        fr--;
        if (luat[dehnod])
            continue;
        if (nod.first == fin and nod.second == 0)
            break;
        cate++;
        //if (cate > lul)
          //  assert(false);
        luat[dehnod] = true;
        int dist = d[dehnod];
        if (nod.second != 0)
        {
            pair<int,int> vec;
            vec = {nod.first,0};
            int dehvec = hsh(vec);
            if (!viz[dehvec] or d[dehvec] > dist)
            {
                viz[dehvec] = 1;
                q[++fr] = (vec);
                d[dehvec] = dist;
            }
            vec = {nod.first + nod.second,nod.second};
            dehvec = hsh(vec);
            if (!viz[dehvec] and vec.first >= 0 and vec.first < n)
            {
                viz[dehvec] = 1;
                q[--bk] = vec;
                d[dehvec] = dist + 1;
            }
            vec = {nod.first - nod.second,nod.second};
            dehvec = hsh(vec);
            if (vec.first >= 0 and vec.first < n and !viz[dehvec])
            {
                viz[dehvec] = 1;
                q[--bk] = vec;
                d[dehvec] = dist + 1;
            }
        }
        else
        {
            for (auto it : what[nod.first])
            {
                pair<int,int> vec = {nod.first,it};
                int dehvec = hsh(vec);
                if (!viz[dehvec] or d[dehvec] > dist)
                {
                    viz[dehvec] = 1;
                    q[++fr] = vec;
                    d[dehvec] = dist;
                }
            }
        }
    }
    if (!viz[hsh({fin,0})])
        cout << -1;
    else
        cout << d[hsh({fin,0})];
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:18: warning: unused variable 'lul' [-Wunused-variable]
   31 |     int cate = 0,lul = 1e6;
      |                  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Correct 0 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1368 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 1112 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 0 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 1 ms 1372 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 3 ms 3416 KB Output is correct
15 Correct 2 ms 1628 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 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 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1368 KB Output is correct
11 Correct 1 ms 1448 KB Output is correct
12 Correct 2 ms 1372 KB Output is correct
13 Correct 1 ms 1624 KB Output is correct
14 Correct 2 ms 2136 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 2 ms 4188 KB Output is correct
18 Correct 1 ms 1120 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 4 ms 9048 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 2436 KB Output is correct
23 Correct 4 ms 7260 KB Output is correct
24 Correct 5 ms 8540 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 4 ms 8028 KB Output is correct
27 Correct 4 ms 8540 KB Output is correct
28 Correct 9 ms 11008 KB Output is correct
29 Correct 17 ms 14296 KB Output is correct
30 Correct 7 ms 10332 KB Output is correct
31 Correct 11 ms 11796 KB Output is correct
32 Correct 9 ms 11024 KB Output is correct
33 Correct 35 ms 20032 KB Output is correct
34 Correct 21 ms 14716 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1180 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1172 KB Output is correct
5 Correct 0 ms 1116 KB Output is correct
6 Correct 0 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 0 ms 1116 KB Output is correct
9 Correct 0 ms 1116 KB Output is correct
10 Correct 1 ms 1600 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 1 ms 1624 KB Output is correct
14 Correct 2 ms 2136 KB Output is correct
15 Correct 1 ms 1696 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 2 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 4 ms 9064 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 6 ms 7260 KB Output is correct
24 Correct 5 ms 8496 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 4 ms 8028 KB Output is correct
27 Correct 4 ms 8540 KB Output is correct
28 Correct 10 ms 11028 KB Output is correct
29 Correct 17 ms 14460 KB Output is correct
30 Correct 7 ms 10332 KB Output is correct
31 Correct 10 ms 11796 KB Output is correct
32 Correct 9 ms 11028 KB Output is correct
33 Correct 34 ms 19992 KB Output is correct
34 Correct 19 ms 14712 KB Output is correct
35 Correct 23 ms 10952 KB Output is correct
36 Correct 3 ms 3676 KB Output is correct
37 Correct 12 ms 11192 KB Output is correct
38 Correct 12 ms 10992 KB Output is correct
39 Correct 4 ms 2652 KB Output is correct
40 Correct 8 ms 8540 KB Output is correct
41 Correct 19 ms 13252 KB Output is correct
42 Correct 6 ms 8536 KB Output is correct
43 Correct 6 ms 9052 KB Output is correct
44 Correct 6 ms 9564 KB Output is correct
45 Correct 151 ms 54060 KB Output is correct
46 Correct 81 ms 32748 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 0 ms 1112 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 0 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 2 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 4 ms 9052 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 4 ms 7260 KB Output is correct
24 Correct 6 ms 8608 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 4 ms 8024 KB Output is correct
27 Correct 6 ms 8536 KB Output is correct
28 Correct 9 ms 11120 KB Output is correct
29 Correct 18 ms 14456 KB Output is correct
30 Correct 7 ms 10332 KB Output is correct
31 Correct 11 ms 11660 KB Output is correct
32 Correct 9 ms 11008 KB Output is correct
33 Correct 33 ms 20024 KB Output is correct
34 Correct 19 ms 14712 KB Output is correct
35 Correct 18 ms 10952 KB Output is correct
36 Correct 2 ms 3756 KB Output is correct
37 Correct 13 ms 11192 KB Output is correct
38 Correct 11 ms 11100 KB Output is correct
39 Correct 5 ms 2628 KB Output is correct
40 Correct 7 ms 8424 KB Output is correct
41 Correct 19 ms 13208 KB Output is correct
42 Correct 6 ms 8540 KB Output is correct
43 Correct 7 ms 9068 KB Output is correct
44 Correct 7 ms 9564 KB Output is correct
45 Correct 174 ms 54076 KB Output is correct
46 Correct 68 ms 32632 KB Output is correct
47 Correct 26 ms 42156 KB Output is correct
48 Correct 6 ms 1884 KB Output is correct
49 Runtime error 6 ms 3416 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -