oj.uz

Submission #469946

# Submission time Handle Problem Language Result Execution time Memory
469946 2021-09-02T11:41:15 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 673 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 = 40000003;
struct mymap
{
    pii* bs = new pii[0];
    int v[mod] = {};
    unsigned char sz[mod] = {};

    int count(int x)
    {
        int y = x%mod;
        if(!sz[y]) return 0;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return 1;
        return 0;
    }

    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};
        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]) if(!d.count(sv<<15^p)) d[sv<<15^p] = 0, q.push_back(sv<<15^p);
    if(!d.count(sv<<15^sp)) d[sv<<15^sp] = 0, 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]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
                }
                if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, 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]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
                }
                if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, 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,40000000,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.count(des<<15^dmy)? d[des<<15^dmy]: -1) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196616 KB Output is correct
2 Correct 82 ms 196648 KB Output is correct
3 Correct 84 ms 196632 KB Output is correct
4 Correct 82 ms 196672 KB Output is correct
5 Correct 81 ms 196584 KB Output is correct
6 Correct 81 ms 196612 KB Output is correct
7 Correct 82 ms 196612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 196676 KB Output is correct
2 Correct 82 ms 196656 KB Output is correct
3 Correct 93 ms 196664 KB Output is correct
4 Correct 84 ms 196612 KB Output is correct
5 Correct 84 ms 196592 KB Output is correct
6 Correct 83 ms 196584 KB Output is correct
7 Correct 84 ms 196676 KB Output is correct
8 Correct 93 ms 196596 KB Output is correct
9 Correct 83 ms 196648 KB Output is correct
10 Correct 86 ms 196736 KB Output is correct
11 Correct 85 ms 196932 KB Output is correct
12 Correct 82 ms 196664 KB Output is correct
13 Correct 82 ms 196656 KB Output is correct
14 Correct 82 ms 196860 KB Output is correct
15 Correct 83 ms 196860 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196672 KB Output is correct
2 Correct 85 ms 196732 KB Output is correct
3 Correct 99 ms 196676 KB Output is correct
4 Correct 81 ms 196676 KB Output is correct
5 Correct 84 ms 196576 KB Output is correct
6 Correct 83 ms 196644 KB Output is correct
7 Correct 83 ms 196672 KB Output is correct
8 Correct 92 ms 196596 KB Output is correct
9 Correct 87 ms 196672 KB Output is correct
10 Correct 85 ms 196672 KB Output is correct
11 Correct 84 ms 196772 KB Output is correct
12 Correct 84 ms 196696 KB Output is correct
13 Correct 87 ms 196672 KB Output is correct
14 Correct 86 ms 196808 KB Output is correct
15 Correct 84 ms 196900 KB Output is correct
16 Correct 86 ms 196696 KB Output is correct
17 Correct 88 ms 197084 KB Output is correct
18 Correct 84 ms 196616 KB Output is correct
19 Correct 81 ms 196676 KB Output is correct
20 Correct 82 ms 196804 KB Output is correct
21 Correct 82 ms 196680 KB Output is correct
22 Correct 83 ms 196688 KB Output is correct
23 Correct 91 ms 196920 KB Output is correct
24 Correct 87 ms 197092 KB Output is correct
25 Correct 91 ms 196968 KB Output is correct
26 Correct 85 ms 196932 KB Output is correct
27 Correct 88 ms 196868 KB Output is correct
28 Correct 90 ms 197412 KB Output is correct
29 Correct 96 ms 198596 KB Output is correct
30 Correct 91 ms 197276 KB Output is correct
31 Correct 95 ms 197744 KB Output is correct
32 Correct 92 ms 197444 KB Output is correct
33 Correct 114 ms 200448 KB Output is correct
34 Correct 108 ms 200420 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196628 KB Output is correct
2 Correct 83 ms 196616 KB Output is correct
3 Correct 83 ms 196676 KB Output is correct
4 Correct 83 ms 196644 KB Output is correct
5 Correct 83 ms 196632 KB Output is correct
6 Correct 85 ms 196680 KB Output is correct
7 Correct 83 ms 196676 KB Output is correct
8 Correct 85 ms 196576 KB Output is correct
9 Correct 84 ms 196632 KB Output is correct
10 Correct 84 ms 196776 KB Output is correct
11 Correct 84 ms 196804 KB Output is correct
12 Correct 82 ms 196612 KB Output is correct
13 Correct 84 ms 196772 KB Output is correct
14 Correct 85 ms 196828 KB Output is correct
15 Correct 83 ms 196808 KB Output is correct
16 Correct 84 ms 196620 KB Output is correct
17 Correct 85 ms 197084 KB Output is correct
18 Correct 83 ms 196676 KB Output is correct
19 Correct 85 ms 196592 KB Output is correct
20 Correct 84 ms 196768 KB Output is correct
21 Correct 85 ms 196680 KB Output is correct
22 Correct 83 ms 196720 KB Output is correct
23 Correct 84 ms 196876 KB Output is correct
24 Correct 88 ms 197128 KB Output is correct
25 Correct 85 ms 196868 KB Output is correct
26 Correct 88 ms 196932 KB Output is correct
27 Correct 86 ms 196844 KB Output is correct
28 Correct 89 ms 197416 KB Output is correct
29 Correct 101 ms 198684 KB Output is correct
30 Correct 89 ms 197136 KB Output is correct
31 Correct 89 ms 197692 KB Output is correct
32 Correct 88 ms 197436 KB Output is correct
33 Correct 110 ms 200388 KB Output is correct
34 Correct 113 ms 200400 KB Output is correct
35 Correct 116 ms 200128 KB Output is correct
36 Correct 95 ms 197320 KB Output is correct
37 Correct 133 ms 202464 KB Output is correct
38 Correct 132 ms 202076 KB Output is correct
39 Correct 130 ms 202072 KB Output is correct
40 Correct 131 ms 202092 KB Output is correct
41 Correct 131 ms 202124 KB Output is correct
42 Correct 92 ms 197036 KB Output is correct
43 Correct 94 ms 197016 KB Output is correct
44 Correct 101 ms 196868 KB Output is correct
45 Correct 182 ms 212160 KB Output is correct
46 Correct 200 ms 212156 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196676 KB Output is correct
2 Correct 85 ms 196644 KB Output is correct
3 Correct 83 ms 196708 KB Output is correct
4 Correct 81 ms 196628 KB Output is correct
5 Correct 85 ms 196672 KB Output is correct
6 Correct 83 ms 196648 KB Output is correct
7 Correct 83 ms 196656 KB Output is correct
8 Correct 84 ms 196580 KB Output is correct
9 Correct 86 ms 196672 KB Output is correct
10 Correct 88 ms 196676 KB Output is correct
11 Correct 89 ms 196864 KB Output is correct
12 Correct 83 ms 196676 KB Output is correct
13 Correct 84 ms 196676 KB Output is correct
14 Correct 88 ms 196816 KB Output is correct
15 Correct 85 ms 196844 KB Output is correct
16 Correct 84 ms 196708 KB Output is correct
17 Correct 87 ms 197268 KB Output is correct
18 Correct 85 ms 196636 KB Output is correct
19 Correct 84 ms 196804 KB Output is correct
20 Correct 84 ms 196828 KB Output is correct
21 Correct 85 ms 196708 KB Output is correct
22 Correct 82 ms 196676 KB Output is correct
23 Correct 88 ms 196932 KB Output is correct
24 Correct 86 ms 197052 KB Output is correct
25 Correct 86 ms 196932 KB Output is correct
26 Correct 85 ms 196932 KB Output is correct
27 Correct 84 ms 196884 KB Output is correct
28 Correct 88 ms 197360 KB Output is correct
29 Correct 98 ms 198628 KB Output is correct
30 Correct 87 ms 197268 KB Output is correct
31 Correct 93 ms 197696 KB Output is correct
32 Correct 88 ms 197444 KB Output is correct
33 Correct 111 ms 200436 KB Output is correct
34 Correct 108 ms 200452 KB Output is correct
35 Correct 113 ms 200140 KB Output is correct
36 Correct 87 ms 197284 KB Output is correct
37 Correct 131 ms 202448 KB Output is correct
38 Correct 130 ms 202052 KB Output is correct
39 Correct 130 ms 202064 KB Output is correct
40 Correct 130 ms 202104 KB Output is correct
41 Correct 132 ms 202064 KB Output is correct
42 Correct 92 ms 196964 KB Output is correct
43 Correct 92 ms 196928 KB Output is correct
44 Correct 88 ms 196840 KB Output is correct
45 Correct 196 ms 212268 KB Output is correct
46 Correct 181 ms 212068 KB Output is correct
47 Correct 298 ms 220340 KB Output is correct
48 Correct 89 ms 197068 KB Output is correct
49 Correct 90 ms 197064 KB Output is correct
50 Correct 85 ms 197060 KB Output is correct
51 Correct 185 ms 207260 KB Output is correct
52 Correct 194 ms 208132 KB Output is correct
53 Correct 118 ms 200140 KB Output is correct
54 Correct 88 ms 197184 KB Output is correct
55 Correct 89 ms 197440 KB Output is correct
56 Correct 100 ms 198512 KB Output is correct
57 Correct 207 ms 210404 KB Output is correct
58 Correct 107 ms 198928 KB Output is correct
59 Correct 119 ms 199876 KB Output is correct
60 Correct 125 ms 200700 KB Output is correct
61 Correct 120 ms 200260 KB Output is correct
62 Correct 243 ms 213016 KB Output is correct
63 Runtime error 673 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -