oj.uz

Submission #469957

# Submission time Handle Problem Language Result Execution time Memory
469957 2021-09-02T12:16:07 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 697 ms 220452 KB 
///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

const int N = 30'010;
const int mod = 10000019;
struct myset
{
    int v[mod][6] = {};
    unsigned char sz[mod] = {};

    bool add(int x)
    {
        int y = x%mod;
        Loop(i,0,sz[y])
            if(v[y][i]==x)
                return 0;
        if(sz[y] == 6) exit(0);
        v[y][sz[y]++] = x;
        return 1;
    }
};
myset d;
vector<int> P[N];
bool vis[N];
int n, m;

int bfs(int sv, int sp, int des)
{
    if(sv == des) return 0;
    vector<int> q, q2;
    vis[sv] = 1;
    for(auto p : P[sv]) if(d.add(sv<<15^p)) q.push_back(sv<<15^p);
    if(d.add(sv<<15^sp)) q.push_back(sv<<15^sp);
    for(int d = 0; q.size();)
    {
        for(ull i = 0; i < q.size(); ++i)
        {
            int v = q[i]>>15, p = q[i]&32767;
            //cerr << v << ' ' << p << ": " << d << '\n';
            int u = v+p;
            if(u == des) return d+1;
            if(0 <= u && u < n)
            {
                if(!vis[u]){
                    vis[u] = 1;
                    for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
                }
                if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
            }
            u = v-p;
            if(u == des) return d+1;
            if(0 <= u && u < n)
            {
                if(!vis[u]){
                    vis[u] = 1;
                    for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
                }
                if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
            }
        }
        q = q2;
        q2.clear();
        ++d;
    }
    return -1;
}

bool isPrime(int n)
{
    for(int d = 2; d*d <= n; ++d)
        if(n%d == 0)
            return 0;
    return 1;
}

int main()
{
    //Loop(i,10000000,INT_MAX) if(isPrime(i)){cout << i;break;}
    FAST;
    cin >> n >> m;
    int p, src, des, dmy;
    cin >> src >> p;
    cin >> des >> dmy;
    P[des].push_back(dmy);
    Loop(i,2,m)
    {
        int v, p;
        cin >> v >> p;
        P[v].push_back(p);
    }
    cout << bfs(src, p, des) << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1968 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1912 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 5 ms 7840 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 10 ms 17436 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 12 ms 20940 KB Output is correct
24 Correct 15 ms 28936 KB Output is correct
25 Correct 5 ms 5324 KB Output is correct
26 Correct 9 ms 15180 KB Output is correct
27 Correct 13 ms 18508 KB Output is correct
28 Correct 20 ms 34028 KB Output is correct
29 Correct 16 ms 19916 KB Output is correct
30 Correct 12 ms 18632 KB Output is correct
31 Correct 13 ms 20428 KB Output is correct
32 Correct 12 ms 20504 KB Output is correct
33 Correct 19 ms 21644 KB Output is correct
34 Correct 18 ms 20436 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 4 ms 7756 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 10 ms 17484 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 11 ms 20940 KB Output is correct
24 Correct 16 ms 29004 KB Output is correct
25 Correct 3 ms 5324 KB Output is correct
26 Correct 9 ms 15180 KB Output is correct
27 Correct 11 ms 18504 KB Output is correct
28 Correct 22 ms 34032 KB Output is correct
29 Correct 16 ms 19932 KB Output is correct
30 Correct 12 ms 18636 KB Output is correct
31 Correct 12 ms 20428 KB Output is correct
32 Correct 12 ms 20428 KB Output is correct
33 Correct 19 ms 21684 KB Output is correct
34 Correct 15 ms 20420 KB Output is correct
35 Correct 37 ms 68616 KB Output is correct
36 Correct 5 ms 8012 KB Output is correct
37 Correct 17 ms 26564 KB Output is correct
38 Correct 38 ms 66408 KB Output is correct
39 Correct 9 ms 1612 KB Output is correct
40 Correct 8 ms 2892 KB Output is correct
41 Correct 38 ms 69604 KB Output is correct
42 Correct 13 ms 15356 KB Output is correct
43 Correct 16 ms 18736 KB Output is correct
44 Correct 14 ms 17676 KB Output is correct
45 Correct 47 ms 30128 KB Output is correct
46 Correct 32 ms 23112 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 5 ms 7756 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 10 ms 17520 KB Output is correct
21 Correct 2 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 11 ms 20940 KB Output is correct
24 Correct 15 ms 28992 KB Output is correct
25 Correct 4 ms 5324 KB Output is correct
26 Correct 11 ms 15180 KB Output is correct
27 Correct 11 ms 18508 KB Output is correct
28 Correct 19 ms 34068 KB Output is correct
29 Correct 14 ms 19916 KB Output is correct
30 Correct 13 ms 18636 KB Output is correct
31 Correct 14 ms 20392 KB Output is correct
32 Correct 15 ms 20444 KB Output is correct
33 Correct 23 ms 21664 KB Output is correct
34 Correct 19 ms 20428 KB Output is correct
35 Correct 38 ms 68676 KB Output is correct
36 Correct 5 ms 8012 KB Output is correct
37 Correct 17 ms 26572 KB Output is correct
38 Correct 39 ms 66428 KB Output is correct
39 Correct 7 ms 1520 KB Output is correct
40 Correct 8 ms 2892 KB Output is correct
41 Correct 38 ms 69572 KB Output is correct
42 Correct 13 ms 15348 KB Output is correct
43 Correct 15 ms 18660 KB Output is correct
44 Correct 14 ms 17612 KB Output is correct
45 Correct 50 ms 30152 KB Output is correct
46 Correct 30 ms 23084 KB Output is correct
47 Correct 37 ms 59108 KB Output is correct
48 Correct 8 ms 1484 KB Output is correct
49 Correct 7 ms 1496 KB Output is correct
50 Correct 5 ms 1356 KB Output is correct
51 Correct 76 ms 135620 KB Output is correct
52 Correct 83 ms 149064 KB Output is correct
53 Correct 28 ms 39108 KB Output is correct
54 Correct 22 ms 40124 KB Output is correct
55 Correct 32 ms 60040 KB Output is correct
56 Correct 47 ms 68708 KB Output is correct
57 Correct 3 ms 4812 KB Output is correct
58 Correct 45 ms 69536 KB Output is correct
59 Correct 49 ms 68360 KB Output is correct
60 Correct 49 ms 68304 KB Output is correct
61 Correct 56 ms 82620 KB Output is correct
62 Correct 166 ms 220452 KB Output is correct
63 Correct 314 ms 141100 KB Output is correct
64 Correct 370 ms 122784 KB Output is correct
65 Correct 521 ms 111000 KB Output is correct
66 Correct 697 ms 100024 KB Output is correct
67 Correct 374 ms 96708 KB Output is correct