oj.uz

Submission #469956

# Submission time Handle Problem Language Result Execution time Memory
469956 2021-09-02T12:15:14 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 162 ms 159528 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;

#pragma GCC optimize("O3,unroll-loops")

const int N = 30'010;
const int mod = 10000019;
struct myset
{
    int v[mod][4] = {};
    unsigned char sz[mod] = {};
    int sum = 0;

    bool add(int x)
    {
        ++sum;
        if(sum > 10'000'000) exit(0);
        int y = x%mod;
        Loop(i,0,sz[y])
            if(v[y][i]==x)
                return 0;
        if(sz[y] == 4) exit(0);
        v[y][sz[y]++] = x;
        return 1;
    }
};
myset 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]) if(d.add(sv<<15^p)) q.push_back(sv<<15^p);
    if(d.add(sv<<15^sp)) 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(u == des) return d+1;
            if(0 <= u && u < n)
            {
                if(!vis[u]){
                    vis[u] = 1;
                    for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
                }
                if(::d.add(u<<15^p)) 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]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
                }
                if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
            }
        }
        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,10000000,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 1 ms 972 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 4 ms 6732 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 10 ms 17356 KB Output is correct
21 Correct 2 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 11 ms 19944 KB Output is correct
24 Correct 15 ms 27828 KB Output is correct
25 Correct 4 ms 5196 KB Output is correct
26 Correct 9 ms 14948 KB Output is correct
27 Correct 10 ms 17740 KB Output is correct
28 Correct 18 ms 31180 KB Output is correct
29 Correct 13 ms 18508 KB Output is correct
30 Correct 11 ms 18508 KB Output is correct
31 Correct 12 ms 18508 KB Output is correct
32 Correct 14 ms 19724 KB Output is correct
33 Correct 19 ms 19776 KB Output is correct
34 Correct 14 ms 18356 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 4 ms 6732 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 10 ms 17288 KB Output is correct
21 Correct 2 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 11 ms 19980 KB Output is correct
24 Correct 14 ms 27928 KB Output is correct
25 Correct 3 ms 5188 KB Output is correct
26 Correct 9 ms 14956 KB Output is correct
27 Correct 10 ms 17740 KB Output is correct
28 Correct 18 ms 31180 KB Output is correct
29 Correct 14 ms 18508 KB Output is correct
30 Correct 13 ms 18508 KB Output is correct
31 Correct 12 ms 18504 KB Output is correct
32 Correct 14 ms 19788 KB Output is correct
33 Correct 20 ms 19800 KB Output is correct
34 Correct 14 ms 18380 KB Output is correct
35 Correct 32 ms 54608 KB Output is correct
36 Correct 6 ms 7628 KB Output is correct
37 Correct 16 ms 22196 KB Output is correct
38 Correct 32 ms 54428 KB Output is correct
39 Correct 9 ms 1432 KB Output is correct
40 Correct 8 ms 2636 KB Output is correct
41 Correct 35 ms 56908 KB Output is correct
42 Correct 14 ms 15180 KB Output is correct
43 Correct 14 ms 17868 KB Output is correct
44 Correct 15 ms 17472 KB Output is correct
45 Correct 46 ms 25764 KB Output is correct
46 Correct 27 ms 21956 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1612 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 2 ms 1912 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 4 ms 6604 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 10 ms 17356 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 13 ms 19916 KB Output is correct
24 Correct 14 ms 27852 KB Output is correct
25 Correct 3 ms 5196 KB Output is correct
26 Correct 9 ms 14924 KB Output is correct
27 Correct 10 ms 17740 KB Output is correct
28 Correct 18 ms 31176 KB Output is correct
29 Correct 13 ms 18508 KB Output is correct
30 Correct 10 ms 18508 KB Output is correct
31 Correct 11 ms 18508 KB Output is correct
32 Correct 13 ms 19788 KB Output is correct
33 Correct 20 ms 19808 KB Output is correct
34 Correct 14 ms 18364 KB Output is correct
35 Correct 33 ms 54596 KB Output is correct
36 Correct 5 ms 7628 KB Output is correct
37 Correct 15 ms 22188 KB Output is correct
38 Correct 33 ms 54432 KB Output is correct
39 Correct 8 ms 1484 KB Output is correct
40 Correct 13 ms 2636 KB Output is correct
41 Correct 34 ms 57000 KB Output is correct
42 Correct 13 ms 15180 KB Output is correct
43 Correct 15 ms 17868 KB Output is correct
44 Correct 15 ms 17528 KB Output is correct
45 Correct 49 ms 25888 KB Output is correct
46 Correct 28 ms 21860 KB Output is correct
47 Correct 38 ms 55028 KB Output is correct
48 Correct 7 ms 1452 KB Output is correct
49 Correct 7 ms 1484 KB Output is correct
50 Correct 6 ms 1396 KB Output is correct
51 Correct 67 ms 117192 KB Output is correct
52 Correct 70 ms 126308 KB Output is correct
53 Correct 27 ms 38036 KB Output is correct
54 Correct 19 ms 33612 KB Output is correct
55 Correct 30 ms 51276 KB Output is correct
56 Correct 43 ms 57156 KB Output is correct
57 Correct 4 ms 4684 KB Output is correct
58 Correct 42 ms 57232 KB Output is correct
59 Correct 39 ms 56364 KB Output is correct
60 Correct 40 ms 56388 KB Output is correct
61 Correct 43 ms 69840 KB Output is correct
62 Correct 139 ms 159528 KB Output is correct
63 Incorrect 162 ms 86632 KB Output isn't correct
64 Halted 0 ms 0 KB -