Submission #469939

#	Time	Username	Problem	Language	Result	Execution time	Memory
469939		ymm	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1049 ms	232936 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 = 6000023;
struct mymap
{
    vector<pii> v[mod];

    int count(int x)
    {
        int y = x%mod;
        for(auto& [a, b] : v[y])
            if(a==x)
                return 1;
        return 0;
    }

    int& operator[](int x)
    {
        int y = x%mod;
        for(auto& [a, b] : v[y])
            if(a==x)
                return b;
        v[y].emplace_back(x,0);
        return v[y].back().S;
    }
};
mymap d;
vector<int> P[N];
bool vis[N];
int n, m;

void bfs(int sv, int sp)
{
    vector<int> q;
    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 i = 0, j = q.size(), d = 0; i < q.size(); j = q.size(), ++d) for(; i < j; ++i)
    {
        if(q.size() > 8'000'000) exit(0);
        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, q.push_back(u<<15^p);
            }
            if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.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, q.push_back(u<<15^p);
            }
            if(!::d.count(u<<15^p)) ::d[u<<15^p] = d+1, q.push_back(u<<15^p);
        }
    }
}

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

int main()
{
    //Loop(i,6000012,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';
}

Compilation message (stderr)

skyscraper.cpp: In function 'void bfs(int, int)':
skyscraper.cpp:57:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0, j = q.size(), d = 0; i < q.size(); j = q.size(), ++d) for(; i < j; ++i)
      |                                         ~~^~~~~~~~~~

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