oj.uz

Submission #469937

# Submission time Handle Problem Language Result Execution time Memory
469937 2021-09-02T11:14:30 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 544 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 = 8000009;
struct mymap
{
    vector<pii> v[mod];

    int count(int x)
    {
        int y = x%mod;
        for(auto& [a, b] : v[y])
            if(a==x)
                return 1;
        return 0;
    }

    int& operator[](int x)
    {
        int y = x%mod;
        for(auto& [a, b] : v[y])
            if(a==x)
                return b;
        v[y].emplace_back(x,0);
        return v[y].back().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,8000000,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:57:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     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 104 ms 188856 KB Output is correct
2 Correct 104 ms 188860 KB Output is correct
3 Correct 98 ms 188780 KB Output is correct
4 Correct 100 ms 188944 KB Output is correct
5 Correct 99 ms 188852 KB Output is correct
6 Correct 98 ms 188844 KB Output is correct
7 Correct 99 ms 188740 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 188768 KB Output is correct
2 Correct 101 ms 188780 KB Output is correct
3 Correct 99 ms 188868 KB Output is correct
4 Correct 102 ms 188856 KB Output is correct
5 Correct 100 ms 188816 KB Output is correct
6 Correct 102 ms 188776 KB Output is correct
7 Correct 99 ms 188836 KB Output is correct
8 Correct 113 ms 188840 KB Output is correct
9 Correct 100 ms 188872 KB Output is correct
10 Correct 100 ms 188832 KB Output is correct
11 Correct 100 ms 189020 KB Output is correct
12 Correct 100 ms 188868 KB Output is correct
13 Correct 101 ms 188812 KB Output is correct
14 Correct 112 ms 189044 KB Output is correct
15 Correct 109 ms 189108 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188744 KB Output is correct
2 Correct 105 ms 188780 KB Output is correct
3 Correct 101 ms 188808 KB Output is correct
4 Correct 104 ms 188848 KB Output is correct
5 Correct 119 ms 188832 KB Output is correct
6 Correct 99 ms 188800 KB Output is correct
7 Correct 100 ms 188872 KB Output is correct
8 Correct 98 ms 188864 KB Output is correct
9 Correct 102 ms 188876 KB Output is correct
10 Correct 113 ms 188932 KB Output is correct
11 Correct 102 ms 189048 KB Output is correct
12 Correct 101 ms 188884 KB Output is correct
13 Correct 115 ms 188824 KB Output is correct
14 Correct 101 ms 189072 KB Output is correct
15 Correct 115 ms 189008 KB Output is correct
16 Correct 102 ms 188820 KB Output is correct
17 Correct 107 ms 189312 KB Output is correct
18 Correct 102 ms 188840 KB Output is correct
19 Correct 100 ms 188868 KB Output is correct
20 Correct 101 ms 189000 KB Output is correct
21 Correct 106 ms 188868 KB Output is correct
22 Correct 100 ms 188808 KB Output is correct
23 Correct 116 ms 189056 KB Output is correct
24 Correct 111 ms 189248 KB Output is correct
25 Correct 105 ms 189052 KB Output is correct
26 Correct 105 ms 189148 KB Output is correct
27 Correct 102 ms 189112 KB Output is correct
28 Correct 113 ms 189720 KB Output is correct
29 Correct 116 ms 190936 KB Output is correct
30 Correct 107 ms 189512 KB Output is correct
31 Correct 109 ms 190084 KB Output is correct
32 Correct 108 ms 189648 KB Output is correct
33 Correct 136 ms 193108 KB Output is correct
34 Correct 140 ms 193048 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188740 KB Output is correct
2 Correct 112 ms 188772 KB Output is correct
3 Correct 109 ms 188868 KB Output is correct
4 Correct 106 ms 188868 KB Output is correct
5 Correct 101 ms 188772 KB Output is correct
6 Correct 100 ms 188764 KB Output is correct
7 Correct 111 ms 188868 KB Output is correct
8 Correct 104 ms 188872 KB Output is correct
9 Correct 104 ms 188864 KB Output is correct
10 Correct 104 ms 188928 KB Output is correct
11 Correct 101 ms 189024 KB Output is correct
12 Correct 104 ms 188868 KB Output is correct
13 Correct 102 ms 188868 KB Output is correct
14 Correct 104 ms 188996 KB Output is correct
15 Correct 99 ms 189100 KB Output is correct
16 Correct 98 ms 188940 KB Output is correct
17 Correct 106 ms 189436 KB Output is correct
18 Correct 102 ms 188844 KB Output is correct
19 Correct 99 ms 188820 KB Output is correct
20 Correct 104 ms 188968 KB Output is correct
21 Correct 98 ms 188848 KB Output is correct
22 Correct 101 ms 189044 KB Output is correct
23 Correct 103 ms 189028 KB Output is correct
24 Correct 103 ms 189260 KB Output is correct
25 Correct 106 ms 189252 KB Output is correct
26 Correct 102 ms 189072 KB Output is correct
27 Correct 102 ms 189024 KB Output is correct
28 Correct 107 ms 189688 KB Output is correct
29 Correct 118 ms 191000 KB Output is correct
30 Correct 110 ms 189440 KB Output is correct
31 Correct 123 ms 190168 KB Output is correct
32 Correct 108 ms 189664 KB Output is correct
33 Correct 131 ms 193008 KB Output is correct
34 Correct 135 ms 193036 KB Output is correct
35 Correct 152 ms 192656 KB Output is correct
36 Correct 114 ms 189536 KB Output is correct
37 Correct 156 ms 195132 KB Output is correct
38 Correct 155 ms 194660 KB Output is correct
39 Correct 157 ms 194728 KB Output is correct
40 Correct 153 ms 194628 KB Output is correct
41 Correct 157 ms 194692 KB Output is correct
42 Correct 107 ms 189252 KB Output is correct
43 Correct 107 ms 189132 KB Output is correct
44 Correct 107 ms 189112 KB Output is correct
45 Correct 234 ms 205912 KB Output is correct
46 Correct 232 ms 205964 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188868 KB Output is correct
2 Correct 102 ms 188912 KB Output is correct
3 Correct 100 ms 188848 KB Output is correct
4 Correct 101 ms 188832 KB Output is correct
5 Correct 106 ms 188776 KB Output is correct
6 Correct 99 ms 188788 KB Output is correct
7 Correct 100 ms 188920 KB Output is correct
8 Correct 100 ms 188784 KB Output is correct
9 Correct 101 ms 188868 KB Output is correct
10 Correct 100 ms 188868 KB Output is correct
11 Correct 100 ms 188980 KB Output is correct
12 Correct 102 ms 188828 KB Output is correct
13 Correct 102 ms 188868 KB Output is correct
14 Correct 104 ms 189040 KB Output is correct
15 Correct 99 ms 189016 KB Output is correct
16 Correct 102 ms 188868 KB Output is correct
17 Correct 106 ms 189312 KB Output is correct
18 Correct 99 ms 188832 KB Output is correct
19 Correct 100 ms 188836 KB Output is correct
20 Correct 100 ms 189004 KB Output is correct
21 Correct 102 ms 188776 KB Output is correct
22 Correct 99 ms 188868 KB Output is correct
23 Correct 115 ms 189048 KB Output is correct
24 Correct 104 ms 189236 KB Output is correct
25 Correct 108 ms 189140 KB Output is correct
26 Correct 104 ms 189148 KB Output is correct
27 Correct 105 ms 189000 KB Output is correct
28 Correct 108 ms 189828 KB Output is correct
29 Correct 116 ms 191004 KB Output is correct
30 Correct 105 ms 189444 KB Output is correct
31 Correct 108 ms 190144 KB Output is correct
32 Correct 109 ms 189628 KB Output is correct
33 Correct 131 ms 193052 KB Output is correct
34 Correct 133 ms 193080 KB Output is correct
35 Correct 135 ms 192576 KB Output is correct
36 Correct 106 ms 189500 KB Output is correct
37 Correct 157 ms 195000 KB Output is correct
38 Correct 153 ms 194724 KB Output is correct
39 Correct 154 ms 194720 KB Output is correct
40 Correct 154 ms 194620 KB Output is correct
41 Correct 154 ms 194600 KB Output is correct
42 Correct 112 ms 189228 KB Output is correct
43 Correct 109 ms 189160 KB Output is correct
44 Correct 106 ms 189000 KB Output is correct
45 Correct 235 ms 206080 KB Output is correct
46 Correct 238 ms 205968 KB Output is correct
47 Correct 352 ms 214568 KB Output is correct
48 Correct 109 ms 189320 KB Output is correct
49 Correct 108 ms 189204 KB Output is correct
50 Correct 105 ms 189200 KB Output is correct
51 Correct 207 ms 200632 KB Output is correct
52 Correct 232 ms 201436 KB Output is correct
53 Correct 135 ms 192604 KB Output is correct
54 Correct 112 ms 189424 KB Output is correct
55 Correct 108 ms 189696 KB Output is correct
56 Correct 130 ms 190856 KB Output is correct
57 Correct 232 ms 204080 KB Output is correct
58 Correct 126 ms 191552 KB Output is correct
59 Correct 134 ms 192308 KB Output is correct
60 Correct 140 ms 193284 KB Output is correct
61 Correct 135 ms 192748 KB Output is correct
62 Correct 262 ms 206788 KB Output is correct
63 Runtime error 544 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -