oj.uz

Submission #469952

# Submission time Handle Problem Language Result Execution time Memory
469952 2021-09-02T11:59:15 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 248260 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& operator[](int x)
    {
        int y = x%mod;
        if(!sz[y]) v[y] = (new pii[3])-bs;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return (bs+v[y])[i].S;
        if(sz[y] == 3) exit(0);
        (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;

int bfs(int sv, int sp, int des)
{
    if(sv == des) return 0;
    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);}
    int sum = 0;
    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(u == des) return d+1;
            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(u == des) return d+1;
            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);}
            }
        }
        sum += q.size();
        if(sum > 8'000'000) exit(0);
        q = q2;
        q2.clear();
        ++d;
    }
    return -1;
}

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);
    }
    cout << bfs(src, p, des) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 123332 KB Output is correct
2 Correct 52 ms 123236 KB Output is correct
3 Correct 56 ms 123192 KB Output is correct
4 Correct 52 ms 123188 KB Output is correct
5 Correct 59 ms 123280 KB Output is correct
6 Correct 53 ms 123256 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 52 ms 123280 KB Output is correct
2 Correct 52 ms 123280 KB Output is correct
3 Correct 61 ms 123296 KB Output is correct
4 Correct 57 ms 123332 KB Output is correct
5 Correct 55 ms 123248 KB Output is correct
6 Correct 54 ms 123212 KB Output is correct
7 Correct 54 ms 123288 KB Output is correct
8 Correct 54 ms 123288 KB Output is correct
9 Correct 53 ms 123276 KB Output is correct
10 Correct 53 ms 123204 KB Output is correct
11 Correct 53 ms 123280 KB Output is correct
12 Correct 54 ms 123292 KB Output is correct
13 Correct 55 ms 123236 KB Output is correct
14 Correct 56 ms 123592 KB Output is correct
15 Correct 54 ms 123396 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 123228 KB Output is correct
2 Correct 62 ms 123312 KB Output is correct
3 Correct 54 ms 123212 KB Output is correct
4 Correct 53 ms 123204 KB Output is correct
5 Correct 52 ms 123208 KB Output is correct
6 Correct 52 ms 123212 KB Output is correct
7 Correct 58 ms 123228 KB Output is correct
8 Correct 54 ms 123252 KB Output is correct
9 Correct 53 ms 123200 KB Output is correct
10 Correct 54 ms 123204 KB Output is correct
11 Correct 52 ms 123284 KB Output is correct
12 Correct 52 ms 123280 KB Output is correct
13 Correct 53 ms 123228 KB Output is correct
14 Correct 54 ms 123460 KB Output is correct
15 Correct 53 ms 123396 KB Output is correct
16 Correct 61 ms 123204 KB Output is correct
17 Correct 53 ms 123340 KB Output is correct
18 Correct 54 ms 123308 KB Output is correct
19 Correct 54 ms 123436 KB Output is correct
20 Correct 61 ms 123400 KB Output is correct
21 Correct 53 ms 123204 KB Output is correct
22 Correct 53 ms 123208 KB Output is correct
23 Correct 54 ms 123436 KB Output is correct
24 Correct 55 ms 123460 KB Output is correct
25 Correct 53 ms 123340 KB Output is correct
26 Correct 54 ms 123356 KB Output is correct
27 Correct 55 ms 123456 KB Output is correct
28 Correct 58 ms 123912 KB Output is correct
29 Correct 75 ms 125124 KB Output is correct
30 Correct 65 ms 123788 KB Output is correct
31 Correct 60 ms 124348 KB Output is correct
32 Correct 58 ms 123952 KB Output is correct
33 Correct 78 ms 127076 KB Output is correct
34 Correct 65 ms 125192 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 123276 KB Output is correct
2 Correct 54 ms 123264 KB Output is correct
3 Correct 53 ms 123228 KB Output is correct
4 Correct 55 ms 123192 KB Output is correct
5 Correct 54 ms 123252 KB Output is correct
6 Correct 55 ms 123308 KB Output is correct
7 Correct 54 ms 123204 KB Output is correct
8 Correct 53 ms 123232 KB Output is correct
9 Correct 53 ms 123272 KB Output is correct
10 Correct 53 ms 123320 KB Output is correct
11 Correct 56 ms 123332 KB Output is correct
12 Correct 53 ms 123268 KB Output is correct
13 Correct 54 ms 123328 KB Output is correct
14 Correct 53 ms 123432 KB Output is correct
15 Correct 53 ms 123312 KB Output is correct
16 Correct 54 ms 123296 KB Output is correct
17 Correct 55 ms 123300 KB Output is correct
18 Correct 58 ms 123272 KB Output is correct
19 Correct 55 ms 123212 KB Output is correct
20 Correct 65 ms 123344 KB Output is correct
21 Correct 57 ms 123320 KB Output is correct
22 Correct 55 ms 123276 KB Output is correct
23 Correct 54 ms 123460 KB Output is correct
24 Correct 56 ms 123552 KB Output is correct
25 Correct 60 ms 123304 KB Output is correct
26 Correct 55 ms 123344 KB Output is correct
27 Correct 55 ms 123460 KB Output is correct
28 Correct 60 ms 123964 KB Output is correct
29 Correct 70 ms 125168 KB Output is correct
30 Correct 57 ms 123744 KB Output is correct
31 Correct 61 ms 124356 KB Output is correct
32 Correct 64 ms 124024 KB Output is correct
33 Correct 95 ms 126976 KB Output is correct
34 Correct 67 ms 125248 KB Output is correct
35 Correct 67 ms 124624 KB Output is correct
36 Correct 56 ms 123344 KB Output is correct
37 Correct 60 ms 123756 KB Output is correct
38 Correct 70 ms 124352 KB Output is correct
39 Correct 61 ms 123448 KB Output is correct
40 Correct 60 ms 123472 KB Output is correct
41 Correct 70 ms 124392 KB Output is correct
42 Correct 58 ms 123488 KB Output is correct
43 Correct 60 ms 123460 KB Output is correct
44 Correct 66 ms 123436 KB Output is correct
45 Correct 166 ms 138720 KB Output is correct
46 Correct 107 ms 131184 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 123256 KB Output is correct
2 Correct 54 ms 123212 KB Output is correct
3 Correct 54 ms 123260 KB Output is correct
4 Correct 53 ms 123204 KB Output is correct
5 Correct 59 ms 123288 KB Output is correct
6 Correct 54 ms 123224 KB Output is correct
7 Correct 55 ms 123280 KB Output is correct
8 Correct 54 ms 123204 KB Output is correct
9 Correct 53 ms 123204 KB Output is correct
10 Correct 54 ms 123324 KB Output is correct
11 Correct 60 ms 123392 KB Output is correct
12 Correct 54 ms 123204 KB Output is correct
13 Correct 54 ms 123280 KB Output is correct
14 Correct 54 ms 123424 KB Output is correct
15 Correct 53 ms 123388 KB Output is correct
16 Correct 56 ms 123204 KB Output is correct
17 Correct 53 ms 123332 KB Output is correct
18 Correct 55 ms 123308 KB Output is correct
19 Correct 53 ms 123316 KB Output is correct
20 Correct 54 ms 123380 KB Output is correct
21 Correct 53 ms 123272 KB Output is correct
22 Correct 53 ms 123328 KB Output is correct
23 Correct 55 ms 123472 KB Output is correct
24 Correct 55 ms 123500 KB Output is correct
25 Correct 54 ms 123264 KB Output is correct
26 Correct 65 ms 123332 KB Output is correct
27 Correct 55 ms 123588 KB Output is correct
28 Correct 59 ms 123968 KB Output is correct
29 Correct 66 ms 125112 KB Output is correct
30 Correct 57 ms 123836 KB Output is correct
31 Correct 59 ms 124356 KB Output is correct
32 Correct 61 ms 123960 KB Output is correct
33 Correct 83 ms 127116 KB Output is correct
34 Correct 65 ms 125292 KB Output is correct
35 Correct 65 ms 124700 KB Output is correct
36 Correct 55 ms 123376 KB Output is correct
37 Correct 59 ms 123836 KB Output is correct
38 Correct 64 ms 124428 KB Output is correct
39 Correct 59 ms 123460 KB Output is correct
40 Correct 59 ms 123504 KB Output is correct
41 Correct 65 ms 124452 KB Output is correct
42 Correct 57 ms 123460 KB Output is correct
43 Correct 58 ms 123632 KB Output is correct
44 Correct 67 ms 123504 KB Output is correct
45 Correct 164 ms 138740 KB Output is correct
46 Correct 105 ms 131268 KB Output is correct
47 Correct 62 ms 124156 KB Output is correct
48 Correct 58 ms 123668 KB Output is correct
49 Correct 60 ms 123748 KB Output is correct
50 Correct 67 ms 123588 KB Output is correct
51 Correct 75 ms 125380 KB Output is correct
52 Correct 78 ms 125600 KB Output is correct
53 Correct 62 ms 124112 KB Output is correct
54 Correct 59 ms 123772 KB Output is correct
55 Correct 63 ms 124100 KB Output is correct
56 Correct 74 ms 125180 KB Output is correct
57 Correct 54 ms 123376 KB Output is correct
58 Correct 78 ms 125516 KB Output is correct
59 Correct 75 ms 125204 KB Output is correct
60 Correct 76 ms 125204 KB Output is correct
61 Correct 74 ms 125148 KB Output is correct
62 Correct 184 ms 138108 KB Output is correct
63 Correct 703 ms 194824 KB Output is correct
64 Correct 814 ms 210992 KB Output is correct
65 Execution timed out 1101 ms 248260 KB Time limit exceeded
66 Halted 0 ms 0 KB -