Submission #469945

#	Time	Username	Problem	Language	Result	Execution time	Memory
469945		ymm	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	271 ms	262148 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;

const int N = 30'010;
const int mod = 50000017;
struct mymap
{
    pii* bs = new pii[0];
    int v[mod] = {};
    unsigned char sz[mod] = {};

    int count(int x)
    {
        int y = x%mod;
        if(!sz[y]) return 0;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return 1;
        return 0;
    }

    int& operator[](int x)
    {
        int y = x%mod;
        if(!sz[y]) v[y] = (new pii[1])-bs, sz[y]=0;
        Loop(i,0,sz[y])
            if((bs+v[y])[i].F==x)
                return (bs+v[y])[i].S;
        if(sz[y] && (sz[y]&-sz[y]) == sz[y]){
            auto tmp = new pii[sz[y]*2];
            Loop(i,0,sz[y]) tmp[i] = (bs+v[y])[i];
            delete[](bs+v[y]);
            v[y] = tmp-bs;
        }
        (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;

void bfs(int sv, int sp)
{
    vector<int> q, q2;
    vis[sv] = 1;
    for(auto p : P[sv]) if(!d.count(sv<<15^p)) d[sv<<15^p] = 0, q.push_back(sv<<15^p);
    if(!d.count(sv<<15^sp)) d[sv<<15^sp] = 0, 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(0 <= u && u < n)
            {
                if(!vis[u]){
                    vis[u] = 1;
                    for(auto p : P[u]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
                }
                if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
            }
            u = v-p;
            if(0 <= u && u < n)
            {
                if(!vis[u]){
                    vis[u] = 1;
                    for(auto p : P[u]) if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
                }
                if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q2.push_back(u<<15^p);
            }
        }
        q = q2;
        q2.clear();
        ++d;
    }
}

bool isPrime(int n)
{
    for(int d = 2; d*d <= n; ++d)
        if(n%d == 0)
            return 0;
    return 1;
}

int main()
{
    //Loop(i,50000000,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);
    }
    bfs(src, p);
    cout << (d.count(des<<15^dmy)? d[des<<15^dmy]: -1) << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43