oj.uz

Submission #469953

# Submission time Handle Problem Language Result Execution time Memory
469953 2021-09-02T12:01:30 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 217080 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 = 20000003;
struct mymap
{
    pii* bs = new pii[0];
    int v[mod] = {};
    unsigned char sz[mod] = {};

    int& operator[](int x)
    {
        int y = x%mod;
        if(!sz[y]) v[y] = (new pii[3])-bs;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return (bs+v[y])[i].S;
        if(sz[y] == 3) exit(0);
        (bs+v[y])[sz[y]++] = {x,0};
        return (bs+v[y])[sz[y]-1].S;
    }
};
mymap 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]) {auto& x = d[sv<<15^p]; if(!x) x = 1, q.push_back(sv<<15^p);}
    {auto& x = d[sv<<15^sp]; if(!x) x = 1, q.push_back(sv<<15^sp);}
    int sum = 0;
    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]) {auto& x = ::d[u<<15^p]; if(!x) x = d+2, q2.push_back(u<<15^p);}
                }
                {auto& x = ::d[u<<15^p]; if(!x) x = d+2, 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]) {auto& x = ::d[u<<15^p]; if(!x) x = d+2, q2.push_back(u<<15^p);}
                }
                {auto& x = ::d[u<<15^p]; if(!x) x = d+2, q2.push_back(u<<15^p);}
            }
        }
        sum += q.size();
        if(sum > 8'000'000) exit(0);
        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,20000000,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 42 ms 98828 KB Output is correct
2 Correct 42 ms 98772 KB Output is correct
3 Correct 43 ms 98856 KB Output is correct
4 Correct 42 ms 98856 KB Output is correct
5 Correct 44 ms 98844 KB Output is correct
6 Correct 42 ms 98760 KB Output is correct
7 Correct 44 ms 98844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98880 KB Output is correct
2 Correct 51 ms 98756 KB Output is correct
3 Correct 42 ms 98828 KB Output is correct
4 Correct 42 ms 98756 KB Output is correct
5 Correct 42 ms 98760 KB Output is correct
6 Correct 40 ms 98760 KB Output is correct
7 Correct 43 ms 98812 KB Output is correct
8 Correct 44 ms 98788 KB Output is correct
9 Correct 43 ms 98760 KB Output is correct
10 Correct 43 ms 98892 KB Output is correct
11 Correct 43 ms 98852 KB Output is correct
12 Correct 43 ms 98756 KB Output is correct
13 Correct 44 ms 98764 KB Output is correct
14 Correct 44 ms 99020 KB Output is correct
15 Correct 45 ms 98948 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 98844 KB Output is correct
2 Correct 43 ms 98828 KB Output is correct
3 Correct 43 ms 98756 KB Output is correct
4 Correct 43 ms 98732 KB Output is correct
5 Correct 42 ms 98840 KB Output is correct
6 Correct 43 ms 98764 KB Output is correct
7 Correct 44 ms 98872 KB Output is correct
8 Correct 43 ms 98800 KB Output is correct
9 Correct 44 ms 98756 KB Output is correct
10 Correct 42 ms 98868 KB Output is correct
11 Correct 42 ms 98800 KB Output is correct
12 Correct 44 ms 98784 KB Output is correct
13 Correct 44 ms 98800 KB Output is correct
14 Correct 44 ms 99012 KB Output is correct
15 Correct 43 ms 98828 KB Output is correct
16 Correct 43 ms 98756 KB Output is correct
17 Correct 43 ms 98868 KB Output is correct
18 Correct 43 ms 98800 KB Output is correct
19 Correct 43 ms 98796 KB Output is correct
20 Correct 44 ms 98992 KB Output is correct
21 Correct 45 ms 98780 KB Output is correct
22 Correct 43 ms 98828 KB Output is correct
23 Correct 47 ms 98920 KB Output is correct
24 Correct 46 ms 99040 KB Output is correct
25 Correct 44 ms 98820 KB Output is correct
26 Correct 44 ms 98868 KB Output is correct
27 Correct 45 ms 98876 KB Output is correct
28 Correct 49 ms 99520 KB Output is correct
29 Correct 59 ms 100668 KB Output is correct
30 Correct 53 ms 99372 KB Output is correct
31 Correct 52 ms 99852 KB Output is correct
32 Correct 50 ms 99524 KB Output is correct
33 Correct 69 ms 102832 KB Output is correct
34 Correct 57 ms 100812 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98800 KB Output is correct
2 Correct 50 ms 98756 KB Output is correct
3 Correct 44 ms 98764 KB Output is correct
4 Correct 44 ms 98764 KB Output is correct
5 Correct 45 ms 98824 KB Output is correct
6 Correct 48 ms 98756 KB Output is correct
7 Correct 50 ms 98756 KB Output is correct
8 Correct 43 ms 98856 KB Output is correct
9 Correct 50 ms 98776 KB Output is correct
10 Correct 42 ms 98832 KB Output is correct
11 Correct 45 ms 98852 KB Output is correct
12 Correct 43 ms 98796 KB Output is correct
13 Correct 42 ms 98844 KB Output is correct
14 Correct 43 ms 99004 KB Output is correct
15 Correct 43 ms 98932 KB Output is correct
16 Correct 42 ms 98808 KB Output is correct
17 Correct 42 ms 98952 KB Output is correct
18 Correct 44 ms 98860 KB Output is correct
19 Correct 44 ms 98748 KB Output is correct
20 Correct 46 ms 98960 KB Output is correct
21 Correct 43 ms 98860 KB Output is correct
22 Correct 42 ms 98836 KB Output is correct
23 Correct 45 ms 98924 KB Output is correct
24 Correct 44 ms 99064 KB Output is correct
25 Correct 44 ms 98884 KB Output is correct
26 Correct 44 ms 98884 KB Output is correct
27 Correct 45 ms 98884 KB Output is correct
28 Correct 49 ms 99408 KB Output is correct
29 Correct 56 ms 100728 KB Output is correct
30 Correct 46 ms 99380 KB Output is correct
31 Correct 48 ms 99788 KB Output is correct
32 Correct 54 ms 99512 KB Output is correct
33 Correct 67 ms 102532 KB Output is correct
34 Correct 56 ms 100748 KB Output is correct
35 Correct 56 ms 100280 KB Output is correct
36 Correct 45 ms 98896 KB Output is correct
37 Correct 53 ms 99404 KB Output is correct
38 Correct 56 ms 99936 KB Output is correct
39 Correct 50 ms 99072 KB Output is correct
40 Correct 51 ms 99188 KB Output is correct
41 Correct 55 ms 100036 KB Output is correct
42 Correct 50 ms 99012 KB Output is correct
43 Correct 50 ms 99024 KB Output is correct
44 Correct 50 ms 98992 KB Output is correct
45 Correct 150 ms 114300 KB Output is correct
46 Correct 83 ms 106736 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98836 KB Output is correct
2 Correct 43 ms 98816 KB Output is correct
3 Correct 43 ms 98736 KB Output is correct
4 Correct 43 ms 98820 KB Output is correct
5 Correct 43 ms 98844 KB Output is correct
6 Correct 42 ms 98828 KB Output is correct
7 Correct 43 ms 98780 KB Output is correct
8 Correct 43 ms 98728 KB Output is correct
9 Correct 43 ms 98764 KB Output is correct
10 Correct 44 ms 98752 KB Output is correct
11 Correct 43 ms 98760 KB Output is correct
12 Correct 51 ms 98760 KB Output is correct
13 Correct 44 ms 98840 KB Output is correct
14 Correct 44 ms 99020 KB Output is correct
15 Correct 44 ms 98900 KB Output is correct
16 Correct 42 ms 98756 KB Output is correct
17 Correct 47 ms 98848 KB Output is correct
18 Correct 43 ms 98756 KB Output is correct
19 Correct 43 ms 98808 KB Output is correct
20 Correct 43 ms 98972 KB Output is correct
21 Correct 43 ms 98764 KB Output is correct
22 Correct 44 ms 98852 KB Output is correct
23 Correct 45 ms 98892 KB Output is correct
24 Correct 45 ms 99040 KB Output is correct
25 Correct 42 ms 98856 KB Output is correct
26 Correct 46 ms 98884 KB Output is correct
27 Correct 45 ms 98896 KB Output is correct
28 Correct 48 ms 99496 KB Output is correct
29 Correct 57 ms 100656 KB Output is correct
30 Correct 45 ms 99364 KB Output is correct
31 Correct 51 ms 99820 KB Output is correct
32 Correct 48 ms 99548 KB Output is correct
33 Correct 69 ms 102504 KB Output is correct
34 Correct 54 ms 100828 KB Output is correct
35 Correct 57 ms 100176 KB Output is correct
36 Correct 44 ms 98892 KB Output is correct
37 Correct 50 ms 99356 KB Output is correct
38 Correct 54 ms 99912 KB Output is correct
39 Correct 49 ms 99056 KB Output is correct
40 Correct 49 ms 99076 KB Output is correct
41 Correct 57 ms 99956 KB Output is correct
42 Correct 49 ms 98988 KB Output is correct
43 Correct 49 ms 99020 KB Output is correct
44 Correct 49 ms 99048 KB Output is correct
45 Correct 145 ms 114316 KB Output is correct
46 Correct 88 ms 106828 KB Output is correct
47 Correct 54 ms 99640 KB Output is correct
48 Correct 48 ms 99236 KB Output is correct
49 Correct 50 ms 99276 KB Output is correct
50 Correct 48 ms 99136 KB Output is correct
51 Correct 67 ms 100908 KB Output is correct
52 Correct 71 ms 101148 KB Output is correct
53 Correct 53 ms 99636 KB Output is correct
54 Correct 48 ms 99220 KB Output is correct
55 Correct 51 ms 99652 KB Output is correct
56 Correct 61 ms 100672 KB Output is correct
57 Correct 47 ms 98840 KB Output is correct
58 Correct 66 ms 100972 KB Output is correct
59 Correct 63 ms 100708 KB Output is correct
60 Correct 64 ms 100848 KB Output is correct
61 Correct 64 ms 100676 KB Output is correct
62 Correct 169 ms 113724 KB Output is correct
63 Correct 703 ms 170332 KB Output is correct
64 Correct 852 ms 186680 KB Output is correct
65 Execution timed out 1101 ms 217080 KB Time limit exceeded
66 Halted 0 ms 0 KB -