oj.uz

Submission #469949

# Submission time Handle Problem Language Result Execution time Memory
469949 2021-09-02T11:50:29 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 262148 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;

const int N = 30'010;
const int mod = 30000001;
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[1])-bs, sz[y]=0;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return (bs+v[y])[i].S;
        if(sz[y] && (sz[y]&-sz[y]) == sz[y]){
            auto tmp = new pii[sz[y]*2];
            Loop(i,0,sz[y]) tmp[i] = (bs+v[y])[i];
            delete[](bs+v[y]);
            v[y] = tmp-bs;
        }
        (bs+v[y])[sz[y]++] = {x,0};
        if(sz[y] > 5) exit(0);
        return (bs+v[y])[sz[y]-1].S;
    }
};
mymap d;
vector<int> P[N];
bool vis[N];
int n, m;

void bfs(int sv, int sp)
{
    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);}
    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(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(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);}
            }
        }
        q = q2;
        q2.clear();
        ++d;
    }
}

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

int main()
{
    //Loop(i,30000000,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);
    }
    bfs(src, p);
    cout << (d[des<<15^dmy]? d[des<<15^dmy]-1: -1) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 147700 KB Output is correct
2 Correct 62 ms 147656 KB Output is correct
3 Correct 66 ms 147740 KB Output is correct
4 Correct 63 ms 147648 KB Output is correct
5 Correct 63 ms 147708 KB Output is correct
6 Correct 64 ms 147732 KB Output is correct
7 Correct 64 ms 147652 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 147652 KB Output is correct
2 Correct 65 ms 147768 KB Output is correct
3 Correct 64 ms 147732 KB Output is correct
4 Correct 63 ms 147732 KB Output is correct
5 Correct 67 ms 147876 KB Output is correct
6 Correct 63 ms 147664 KB Output is correct
7 Correct 66 ms 147800 KB Output is correct
8 Correct 63 ms 147700 KB Output is correct
9 Correct 63 ms 147756 KB Output is correct
10 Correct 64 ms 147712 KB Output is correct
11 Correct 65 ms 147952 KB Output is correct
12 Correct 65 ms 147756 KB Output is correct
13 Correct 63 ms 147672 KB Output is correct
14 Correct 65 ms 147964 KB Output is correct
15 Correct 65 ms 147896 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 147640 KB Output is correct
2 Correct 64 ms 147684 KB Output is correct
3 Correct 64 ms 147756 KB Output is correct
4 Correct 63 ms 147668 KB Output is correct
5 Correct 63 ms 147776 KB Output is correct
6 Correct 63 ms 147764 KB Output is correct
7 Correct 64 ms 147652 KB Output is correct
8 Correct 69 ms 147720 KB Output is correct
9 Correct 63 ms 147656 KB Output is correct
10 Correct 64 ms 147808 KB Output is correct
11 Correct 66 ms 147896 KB Output is correct
12 Correct 63 ms 147756 KB Output is correct
13 Correct 64 ms 147892 KB Output is correct
14 Correct 64 ms 147912 KB Output is correct
15 Correct 65 ms 148060 KB Output is correct
16 Correct 64 ms 147768 KB Output is correct
17 Correct 72 ms 148164 KB Output is correct
18 Correct 64 ms 147784 KB Output is correct
19 Correct 65 ms 147700 KB Output is correct
20 Correct 66 ms 147788 KB Output is correct
21 Correct 64 ms 147716 KB Output is correct
22 Correct 65 ms 147776 KB Output is correct
23 Correct 68 ms 147920 KB Output is correct
24 Correct 70 ms 148128 KB Output is correct
25 Correct 67 ms 148032 KB Output is correct
26 Correct 65 ms 147920 KB Output is correct
27 Correct 67 ms 147964 KB Output is correct
28 Correct 71 ms 148432 KB Output is correct
29 Correct 77 ms 149596 KB Output is correct
30 Correct 70 ms 148316 KB Output is correct
31 Correct 87 ms 148800 KB Output is correct
32 Correct 70 ms 148500 KB Output is correct
33 Correct 90 ms 151496 KB Output is correct
34 Correct 88 ms 151492 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 147672 KB Output is correct
2 Correct 63 ms 147780 KB Output is correct
3 Correct 65 ms 147768 KB Output is correct
4 Correct 66 ms 147652 KB Output is correct
5 Correct 63 ms 147756 KB Output is correct
6 Correct 65 ms 147668 KB Output is correct
7 Correct 64 ms 147668 KB Output is correct
8 Correct 64 ms 147732 KB Output is correct
9 Correct 63 ms 147668 KB Output is correct
10 Correct 63 ms 147780 KB Output is correct
11 Correct 64 ms 147924 KB Output is correct
12 Correct 65 ms 147768 KB Output is correct
13 Correct 62 ms 147688 KB Output is correct
14 Correct 63 ms 147912 KB Output is correct
15 Correct 64 ms 147984 KB Output is correct
16 Correct 63 ms 147724 KB Output is correct
17 Correct 67 ms 148188 KB Output is correct
18 Correct 63 ms 147720 KB Output is correct
19 Correct 65 ms 147788 KB Output is correct
20 Correct 67 ms 147792 KB Output is correct
21 Correct 63 ms 147764 KB Output is correct
22 Correct 64 ms 147872 KB Output is correct
23 Correct 66 ms 147928 KB Output is correct
24 Correct 70 ms 148136 KB Output is correct
25 Correct 68 ms 148032 KB Output is correct
26 Correct 69 ms 147940 KB Output is correct
27 Correct 65 ms 147984 KB Output is correct
28 Correct 69 ms 148448 KB Output is correct
29 Correct 75 ms 149608 KB Output is correct
30 Correct 67 ms 148200 KB Output is correct
31 Correct 72 ms 148796 KB Output is correct
32 Correct 70 ms 148652 KB Output is correct
33 Correct 105 ms 151540 KB Output is correct
34 Correct 91 ms 151504 KB Output is correct
35 Correct 93 ms 151224 KB Output is correct
36 Correct 69 ms 148284 KB Output is correct
37 Correct 109 ms 153412 KB Output is correct
38 Correct 114 ms 153152 KB Output is correct
39 Correct 114 ms 153296 KB Output is correct
40 Correct 113 ms 153152 KB Output is correct
41 Correct 112 ms 153156 KB Output is correct
42 Correct 71 ms 148096 KB Output is correct
43 Correct 71 ms 148020 KB Output is correct
44 Correct 70 ms 147952 KB Output is correct
45 Correct 175 ms 163212 KB Output is correct
46 Correct 170 ms 163140 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 147652 KB Output is correct
2 Correct 63 ms 147748 KB Output is correct
3 Correct 64 ms 147776 KB Output is correct
4 Correct 63 ms 147680 KB Output is correct
5 Correct 70 ms 147708 KB Output is correct
6 Correct 63 ms 147712 KB Output is correct
7 Correct 62 ms 147728 KB Output is correct
8 Correct 63 ms 147724 KB Output is correct
9 Correct 64 ms 147668 KB Output is correct
10 Correct 63 ms 147812 KB Output is correct
11 Correct 72 ms 147832 KB Output is correct
12 Correct 66 ms 147796 KB Output is correct
13 Correct 65 ms 147668 KB Output is correct
14 Correct 63 ms 147908 KB Output is correct
15 Correct 65 ms 147968 KB Output is correct
16 Correct 64 ms 147672 KB Output is correct
17 Correct 67 ms 148172 KB Output is correct
18 Correct 65 ms 147708 KB Output is correct
19 Correct 66 ms 147720 KB Output is correct
20 Correct 64 ms 147784 KB Output is correct
21 Correct 66 ms 147784 KB Output is correct
22 Correct 63 ms 147748 KB Output is correct
23 Correct 65 ms 147944 KB Output is correct
24 Correct 68 ms 148196 KB Output is correct
25 Correct 67 ms 148036 KB Output is correct
26 Correct 65 ms 147908 KB Output is correct
27 Correct 65 ms 147936 KB Output is correct
28 Correct 73 ms 148484 KB Output is correct
29 Correct 77 ms 149672 KB Output is correct
30 Correct 67 ms 148292 KB Output is correct
31 Correct 71 ms 148716 KB Output is correct
32 Correct 69 ms 148416 KB Output is correct
33 Correct 93 ms 151516 KB Output is correct
34 Correct 92 ms 151520 KB Output is correct
35 Correct 94 ms 151224 KB Output is correct
36 Correct 70 ms 148316 KB Output is correct
37 Correct 113 ms 153412 KB Output is correct
38 Correct 114 ms 153204 KB Output is correct
39 Correct 119 ms 153116 KB Output is correct
40 Correct 114 ms 153204 KB Output is correct
41 Correct 116 ms 153136 KB Output is correct
42 Correct 74 ms 148092 KB Output is correct
43 Correct 74 ms 148052 KB Output is correct
44 Correct 71 ms 147976 KB Output is correct
45 Correct 174 ms 163192 KB Output is correct
46 Correct 172 ms 163208 KB Output is correct
47 Correct 294 ms 171424 KB Output is correct
48 Correct 68 ms 148148 KB Output is correct
49 Correct 69 ms 148128 KB Output is correct
50 Correct 68 ms 148072 KB Output is correct
51 Correct 161 ms 158352 KB Output is correct
52 Correct 167 ms 159264 KB Output is correct
53 Correct 100 ms 151100 KB Output is correct
54 Correct 68 ms 148220 KB Output is correct
55 Correct 71 ms 148536 KB Output is correct
56 Correct 82 ms 149640 KB Output is correct
57 Correct 185 ms 161392 KB Output is correct
58 Correct 89 ms 149908 KB Output is correct
59 Correct 95 ms 150876 KB Output is correct
60 Correct 104 ms 151716 KB Output is correct
61 Correct 102 ms 151304 KB Output is correct
62 Correct 209 ms 163980 KB Output is correct
63 Correct 717 ms 219572 KB Output is correct
64 Correct 816 ms 235768 KB Output is correct
65 Execution timed out 1065 ms 262148 KB Time limit exceeded
66 Halted 0 ms 0 KB -