oj.uz

Submission #469960

# Submission time Handle Problem Language Result Execution time Memory
469960 2021-09-02T12:38:15 Z ymm Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 13 ms 1996 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;
int mod;
struct myset
{
    int v[10000000+32768][6] = {};
    unsigned char sz[10000000+32768] = {};

    bool add(int x)
    {
        int y = x%mod;
        Loop(i,0,sz[y])
            if(v[y][i]==x)
                return 0;
        if(sz[y] == 6) 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)
{
    if(n%2 == 0) return n==2;
    for(int d = 3; d*d <= n; d += 2)
        if(n%d == 0)
            return 0;
    return 1;
}

int main()
{
    srand(time(0));
    for(;;){int x = 10000000+rand(); if(isPrime(x)){mod=x; 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 2 ms 1868 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 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct

Subtask #3
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 1868 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 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Runtime error 13 ms 1868 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #4
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 1868 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 1996 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Runtime error 13 ms 1860 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

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 1868 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 1996 KB Output is correct
14 Correct 2 ms 1996 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Runtime error 13 ms 1856 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -