oj.uz

Submission #469942

# Submission time Handle Problem Language Result Execution time Memory
469942 2021-09-02T11:31:32 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 = 25000009;
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;
    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 i = 0, j = q.size(), d = 0; i < q.size(); j = q.size(), ++d) for(; i < j; ++i)
    {
        if(q.size() > 8'000'000) exit(0);
        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, q.push_back(u<<15^p);
            }
            if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.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, q.push_back(u<<15^p);
            }
            if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.push_back(u<<15^p);
        }
    }
}

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

int main()
{
    //Loop(i,25000000,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';
}

Compilation message

skyscraper.cpp: In function 'void bfs(int, int)':
skyscraper.cpp:67:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0, j = q.size(), d = 0; i < q.size(); j = q.size(), ++d) for(; i < j; ++i)
      |                                         ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123204 KB Output is correct
2 Correct 52 ms 123308 KB Output is correct
3 Correct 52 ms 123228 KB Output is correct
4 Correct 52 ms 123248 KB Output is correct
5 Correct 51 ms 123228 KB Output is correct
6 Correct 54 ms 123264 KB Output is correct
7 Correct 51 ms 123204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 123204 KB Output is correct
2 Correct 53 ms 123272 KB Output is correct
3 Correct 53 ms 123252 KB Output is correct
4 Correct 52 ms 123196 KB Output is correct
5 Correct 52 ms 123284 KB Output is correct
6 Correct 54 ms 123284 KB Output is correct
7 Correct 52 ms 123204 KB Output is correct
8 Correct 52 ms 123224 KB Output is correct
9 Correct 52 ms 123300 KB Output is correct
10 Correct 53 ms 123320 KB Output is correct
11 Correct 54 ms 123376 KB Output is correct
12 Correct 52 ms 123328 KB Output is correct
13 Correct 53 ms 123260 KB Output is correct
14 Correct 52 ms 123548 KB Output is correct
15 Correct 51 ms 123428 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123264 KB Output is correct
2 Correct 54 ms 123248 KB Output is correct
3 Correct 53 ms 123280 KB Output is correct
4 Correct 52 ms 123252 KB Output is correct
5 Correct 52 ms 123256 KB Output is correct
6 Correct 54 ms 123192 KB Output is correct
7 Correct 53 ms 123328 KB Output is correct
8 Correct 50 ms 123208 KB Output is correct
9 Correct 52 ms 123248 KB Output is correct
10 Correct 53 ms 123336 KB Output is correct
11 Correct 53 ms 123536 KB Output is correct
12 Correct 52 ms 123292 KB Output is correct
13 Correct 62 ms 123204 KB Output is correct
14 Correct 54 ms 123460 KB Output is correct
15 Correct 54 ms 123480 KB Output is correct
16 Correct 54 ms 123204 KB Output is correct
17 Correct 55 ms 123752 KB Output is correct
18 Correct 52 ms 123332 KB Output is correct
19 Correct 53 ms 123204 KB Output is correct
20 Correct 54 ms 123396 KB Output is correct
21 Correct 52 ms 123260 KB Output is correct
22 Correct 54 ms 123332 KB Output is correct
23 Correct 54 ms 123536 KB Output is correct
24 Correct 54 ms 123736 KB Output is correct
25 Correct 56 ms 123536 KB Output is correct
26 Correct 54 ms 123588 KB Output is correct
27 Correct 54 ms 123516 KB Output is correct
28 Correct 58 ms 124156 KB Output is correct
29 Correct 65 ms 125448 KB Output is correct
30 Correct 60 ms 123904 KB Output is correct
31 Correct 59 ms 124496 KB Output is correct
32 Correct 60 ms 124132 KB Output is correct
33 Correct 87 ms 127496 KB Output is correct
34 Correct 79 ms 127492 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123228 KB Output is correct
2 Correct 54 ms 123272 KB Output is correct
3 Correct 52 ms 123224 KB Output is correct
4 Correct 55 ms 123332 KB Output is correct
5 Correct 52 ms 123272 KB Output is correct
6 Correct 61 ms 123200 KB Output is correct
7 Correct 52 ms 123240 KB Output is correct
8 Correct 53 ms 123200 KB Output is correct
9 Correct 52 ms 123284 KB Output is correct
10 Correct 54 ms 123320 KB Output is correct
11 Correct 56 ms 123444 KB Output is correct
12 Correct 52 ms 123328 KB Output is correct
13 Correct 54 ms 123220 KB Output is correct
14 Correct 55 ms 123460 KB Output is correct
15 Correct 55 ms 123460 KB Output is correct
16 Correct 56 ms 123324 KB Output is correct
17 Correct 64 ms 123768 KB Output is correct
18 Correct 54 ms 123280 KB Output is correct
19 Correct 54 ms 123284 KB Output is correct
20 Correct 53 ms 123432 KB Output is correct
21 Correct 52 ms 123208 KB Output is correct
22 Correct 55 ms 123356 KB Output is correct
23 Correct 55 ms 123516 KB Output is correct
24 Correct 56 ms 123696 KB Output is correct
25 Correct 55 ms 123572 KB Output is correct
26 Correct 57 ms 123472 KB Output is correct
27 Correct 55 ms 123460 KB Output is correct
28 Correct 59 ms 124128 KB Output is correct
29 Correct 65 ms 125396 KB Output is correct
30 Correct 57 ms 123856 KB Output is correct
31 Correct 60 ms 124620 KB Output is correct
32 Correct 59 ms 124048 KB Output is correct
33 Correct 80 ms 127500 KB Output is correct
34 Correct 77 ms 127460 KB Output is correct
35 Correct 82 ms 127028 KB Output is correct
36 Correct 59 ms 123972 KB Output is correct
37 Correct 98 ms 129428 KB Output is correct
38 Correct 99 ms 129080 KB Output is correct
39 Correct 97 ms 129136 KB Output is correct
40 Correct 101 ms 129088 KB Output is correct
41 Correct 98 ms 129120 KB Output is correct
42 Correct 60 ms 123684 KB Output is correct
43 Correct 59 ms 123592 KB Output is correct
44 Correct 61 ms 123716 KB Output is correct
45 Correct 154 ms 140484 KB Output is correct
46 Correct 170 ms 140308 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123260 KB Output is correct
2 Correct 53 ms 123300 KB Output is correct
3 Correct 52 ms 123208 KB Output is correct
4 Correct 52 ms 123312 KB Output is correct
5 Correct 53 ms 123316 KB Output is correct
6 Correct 53 ms 123204 KB Output is correct
7 Correct 52 ms 123256 KB Output is correct
8 Correct 53 ms 123288 KB Output is correct
9 Correct 51 ms 123356 KB Output is correct
10 Correct 55 ms 123332 KB Output is correct
11 Correct 52 ms 123460 KB Output is correct
12 Correct 56 ms 123312 KB Output is correct
13 Correct 53 ms 123208 KB Output is correct
14 Correct 54 ms 123456 KB Output is correct
15 Correct 53 ms 123516 KB Output is correct
16 Correct 53 ms 123288 KB Output is correct
17 Correct 57 ms 123732 KB Output is correct
18 Correct 52 ms 123336 KB Output is correct
19 Correct 53 ms 123276 KB Output is correct
20 Correct 54 ms 123328 KB Output is correct
21 Correct 53 ms 123328 KB Output is correct
22 Correct 57 ms 123284 KB Output is correct
23 Correct 55 ms 123480 KB Output is correct
24 Correct 56 ms 123676 KB Output is correct
25 Correct 55 ms 123536 KB Output is correct
26 Correct 54 ms 123596 KB Output is correct
27 Correct 56 ms 123536 KB Output is correct
28 Correct 60 ms 124112 KB Output is correct
29 Correct 65 ms 125396 KB Output is correct
30 Correct 54 ms 123880 KB Output is correct
31 Correct 60 ms 124520 KB Output is correct
32 Correct 62 ms 124116 KB Output is correct
33 Correct 80 ms 127548 KB Output is correct
34 Correct 81 ms 127568 KB Output is correct
35 Correct 82 ms 127008 KB Output is correct
36 Correct 60 ms 123948 KB Output is correct
37 Correct 98 ms 129452 KB Output is correct
38 Correct 102 ms 129080 KB Output is correct
39 Correct 93 ms 129164 KB Output is correct
40 Correct 100 ms 129160 KB Output is correct
41 Correct 102 ms 129136 KB Output is correct
42 Correct 63 ms 123588 KB Output is correct
43 Correct 60 ms 123660 KB Output is correct
44 Correct 57 ms 123460 KB Output is correct
45 Correct 163 ms 140424 KB Output is correct
46 Correct 154 ms 140336 KB Output is correct
47 Correct 265 ms 149416 KB Output is correct
48 Correct 59 ms 123740 KB Output is correct
49 Correct 63 ms 123716 KB Output is correct
50 Correct 56 ms 123588 KB Output is correct
51 Correct 153 ms 135020 KB Output is correct
52 Correct 155 ms 136008 KB Output is correct
53 Correct 93 ms 127048 KB Output is correct
54 Correct 57 ms 123820 KB Output is correct
55 Correct 61 ms 124184 KB Output is correct
56 Correct 70 ms 125320 KB Output is correct
57 Correct 165 ms 138556 KB Output is correct
58 Correct 80 ms 126120 KB Output is correct
59 Correct 85 ms 126864 KB Output is correct
60 Correct 93 ms 127836 KB Output is correct
61 Correct 87 ms 127284 KB Output is correct
62 Correct 195 ms 141408 KB Output is correct
63 Correct 657 ms 205340 KB Output is correct
64 Correct 798 ms 222028 KB Output is correct
65 Execution timed out 1068 ms 262148 KB Time limit exceeded
66 Halted 0 ms 0 KB -