oj.uz

Submission #469943

# Submission time Handle Problem Language Result Execution time Memory
469943 2021-09-02T11:33:47 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() > 4'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 54 ms 123204 KB Output is correct
2 Correct 52 ms 123300 KB Output is correct
3 Correct 52 ms 123224 KB Output is correct
4 Correct 55 ms 123192 KB Output is correct
5 Correct 55 ms 123272 KB Output is correct
6 Correct 55 ms 123216 KB Output is correct
7 Correct 54 ms 123204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 123228 KB Output is correct
2 Correct 55 ms 123212 KB Output is correct
3 Correct 53 ms 123204 KB Output is correct
4 Correct 53 ms 123280 KB Output is correct
5 Correct 54 ms 123284 KB Output is correct
6 Correct 54 ms 123200 KB Output is correct
7 Correct 54 ms 123188 KB Output is correct
8 Correct 54 ms 123300 KB Output is correct
9 Correct 54 ms 123240 KB Output is correct
10 Correct 53 ms 123332 KB Output is correct
11 Correct 57 ms 123460 KB Output is correct
12 Correct 55 ms 123264 KB Output is correct
13 Correct 54 ms 123252 KB Output is correct
14 Correct 54 ms 123460 KB Output is correct
15 Correct 55 ms 123528 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 123212 KB Output is correct
2 Correct 57 ms 123308 KB Output is correct
3 Correct 57 ms 123204 KB Output is correct
4 Correct 52 ms 123236 KB Output is correct
5 Correct 54 ms 123308 KB Output is correct
6 Correct 52 ms 123304 KB Output is correct
7 Correct 54 ms 123204 KB Output is correct
8 Correct 53 ms 123208 KB Output is correct
9 Correct 56 ms 123280 KB Output is correct
10 Correct 52 ms 123292 KB Output is correct
11 Correct 56 ms 123456 KB Output is correct
12 Correct 52 ms 123320 KB Output is correct
13 Correct 56 ms 123236 KB Output is correct
14 Correct 52 ms 123528 KB Output is correct
15 Correct 54 ms 123440 KB Output is correct
16 Correct 55 ms 123292 KB Output is correct
17 Correct 60 ms 123792 KB Output is correct
18 Correct 53 ms 123316 KB Output is correct
19 Correct 53 ms 123324 KB Output is correct
20 Correct 55 ms 123356 KB Output is correct
21 Correct 51 ms 123220 KB Output is correct
22 Correct 55 ms 123324 KB Output is correct
23 Correct 55 ms 123468 KB Output is correct
24 Correct 56 ms 123800 KB Output is correct
25 Correct 58 ms 123548 KB Output is correct
26 Correct 57 ms 123600 KB Output is correct
27 Correct 55 ms 123472 KB Output is correct
28 Correct 61 ms 124104 KB Output is correct
29 Correct 64 ms 125488 KB Output is correct
30 Correct 59 ms 123868 KB Output is correct
31 Correct 61 ms 124520 KB Output is correct
32 Correct 58 ms 124100 KB Output is correct
33 Correct 82 ms 127556 KB Output is correct
34 Correct 85 ms 127524 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 123204 KB Output is correct
2 Correct 52 ms 123204 KB Output is correct
3 Correct 55 ms 123220 KB Output is correct
4 Correct 58 ms 123284 KB Output is correct
5 Correct 54 ms 123204 KB Output is correct
6 Correct 54 ms 123332 KB Output is correct
7 Correct 56 ms 123264 KB Output is correct
8 Correct 59 ms 123256 KB Output is correct
9 Correct 54 ms 123268 KB Output is correct
10 Correct 54 ms 123304 KB Output is correct
11 Correct 55 ms 123384 KB Output is correct
12 Correct 65 ms 123296 KB Output is correct
13 Correct 54 ms 123332 KB Output is correct
14 Correct 55 ms 123516 KB Output is correct
15 Correct 57 ms 123444 KB Output is correct
16 Correct 57 ms 123316 KB Output is correct
17 Correct 60 ms 123788 KB Output is correct
18 Correct 55 ms 123244 KB Output is correct
19 Correct 55 ms 123224 KB Output is correct
20 Correct 56 ms 123392 KB Output is correct
21 Correct 58 ms 123204 KB Output is correct
22 Correct 54 ms 123332 KB Output is correct
23 Correct 55 ms 123536 KB Output is correct
24 Correct 58 ms 123788 KB Output is correct
25 Correct 58 ms 123588 KB Output is correct
26 Correct 56 ms 123480 KB Output is correct
27 Correct 55 ms 123516 KB Output is correct
28 Correct 59 ms 124088 KB Output is correct
29 Correct 66 ms 125416 KB Output is correct
30 Correct 62 ms 123912 KB Output is correct
31 Correct 62 ms 124512 KB Output is correct
32 Correct 59 ms 124096 KB Output is correct
33 Correct 84 ms 127548 KB Output is correct
34 Correct 79 ms 127556 KB Output is correct
35 Correct 92 ms 127204 KB Output is correct
36 Correct 59 ms 123948 KB Output is correct
37 Correct 105 ms 129616 KB Output is correct
38 Correct 117 ms 129120 KB Output is correct
39 Correct 100 ms 129100 KB Output is correct
40 Correct 100 ms 129080 KB Output is correct
41 Correct 105 ms 129108 KB Output is correct
42 Correct 59 ms 123784 KB Output is correct
43 Correct 59 ms 123616 KB Output is correct
44 Correct 58 ms 123528 KB Output is correct
45 Correct 156 ms 140352 KB Output is correct
46 Correct 155 ms 140592 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 123244 KB Output is correct
2 Correct 60 ms 123284 KB Output is correct
3 Correct 54 ms 123228 KB Output is correct
4 Correct 51 ms 123244 KB Output is correct
5 Correct 53 ms 123212 KB Output is correct
6 Correct 53 ms 123236 KB Output is correct
7 Correct 52 ms 123308 KB Output is correct
8 Correct 52 ms 123220 KB Output is correct
9 Correct 53 ms 123220 KB Output is correct
10 Correct 52 ms 123300 KB Output is correct
11 Correct 53 ms 123460 KB Output is correct
12 Correct 53 ms 123248 KB Output is correct
13 Correct 53 ms 123300 KB Output is correct
14 Correct 53 ms 123460 KB Output is correct
15 Correct 55 ms 123468 KB Output is correct
16 Correct 51 ms 123204 KB Output is correct
17 Correct 58 ms 123776 KB Output is correct
18 Correct 55 ms 123332 KB Output is correct
19 Correct 52 ms 123240 KB Output is correct
20 Correct 59 ms 123396 KB Output is correct
21 Correct 55 ms 123260 KB Output is correct
22 Correct 55 ms 123332 KB Output is correct
23 Correct 55 ms 123504 KB Output is correct
24 Correct 56 ms 123680 KB Output is correct
25 Correct 58 ms 123612 KB Output is correct
26 Correct 55 ms 123588 KB Output is correct
27 Correct 54 ms 123544 KB Output is correct
28 Correct 59 ms 124104 KB Output is correct
29 Correct 67 ms 125376 KB Output is correct
30 Correct 58 ms 123980 KB Output is correct
31 Correct 60 ms 124560 KB Output is correct
32 Correct 59 ms 124100 KB Output is correct
33 Correct 77 ms 127580 KB Output is correct
34 Correct 77 ms 127548 KB Output is correct
35 Correct 83 ms 127168 KB Output is correct
36 Correct 58 ms 123928 KB Output is correct
37 Correct 101 ms 129468 KB Output is correct
38 Correct 97 ms 129080 KB Output is correct
39 Correct 101 ms 129256 KB Output is correct
40 Correct 101 ms 129120 KB Output is correct
41 Correct 99 ms 129080 KB Output is correct
42 Correct 61 ms 123588 KB Output is correct
43 Correct 59 ms 123656 KB Output is correct
44 Correct 59 ms 123460 KB Output is correct
45 Correct 151 ms 140372 KB Output is correct
46 Correct 153 ms 140480 KB Output is correct
47 Correct 270 ms 149408 KB Output is correct
48 Correct 60 ms 123728 KB Output is correct
49 Correct 60 ms 123716 KB Output is correct
50 Correct 56 ms 123600 KB Output is correct
51 Correct 152 ms 134980 KB Output is correct
52 Correct 155 ms 135976 KB Output is correct
53 Correct 92 ms 127388 KB Output is correct
54 Correct 60 ms 123788 KB Output is correct
55 Correct 60 ms 124228 KB Output is correct
56 Correct 69 ms 125252 KB Output is correct
57 Correct 164 ms 138560 KB Output is correct
58 Correct 77 ms 126016 KB Output is correct
59 Correct 88 ms 126756 KB Output is correct
60 Correct 95 ms 127740 KB Output is correct
61 Correct 89 ms 127292 KB Output is correct
62 Correct 202 ms 141500 KB Output is correct
63 Correct 694 ms 205420 KB Output is correct
64 Correct 798 ms 222056 KB Output is correct
65 Execution timed out 1074 ms 262148 KB Time limit exceeded
66 Halted 0 ms 0 KB -