Submission #469956

#	Time	Username	Problem	Language	Result	Execution time	Memory
469956		ymm	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	162 ms	159528 KiB

skyscraper

///
///   ♪ 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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43