Submission #469954

#	Time	Username	Problem	Language	Result	Execution time	Memory
469954		ymm	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1098 ms	216864 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 = 20000003;
struct mymap
{
    pii* bs = new pii[0];
    int v[mod] = {};
    unsigned char sz[mod] = {};
    int sum = 0;

    int& operator[](int x)
    {
        ++sum;
        if(sum > 10'000'000) exit(0);
        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);}
    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);}
            }
        }
        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,20000000,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