Submission #160937

#	Time	Username	Problem	Language	Result	Execution time	Memory
160937		nvmdava	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	200 ms	147192 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 30002
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

vector<int> pl[30005];
bool in[N];
bool calc[230000000];
vector<int> asd = {220000871, 220002131, 220002631};

queue<pair<int, int> > q;

int pri, pr2;

int hasher(int a){
	return 1LL * a * a % pri * a % pr2;
}
void insert(int s, int v){
	if(in[s]) return;
	in[s] = 1;

	for(auto x : pl[s]){
		int w = hasher(s * N + x);
		if(calc[w])
			continue;
		q.push({s * N + x, v});
		calc[w] = 1;
	}
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, s, e;
    cin>>n>>m;

    pri = asd[rng() % 3];
    pr2 = asd[rng() % 3];

    for(int i = 1, b, p; i <= m; i++){
    	cin>>b>>p;
    	pl[b].push_back(p);
    	if(i == 1)
    		s = b;
    	else if(i == 2)
    		e = b;
    }
    if(s == e){
    	cout<<0;
    	return 0;
    }
    insert(s, 0);
    while(!q.empty()){
    	int b = q.front().ff / N;
    	int p = q.front().ff % N;
    	int v = q.front().ss;

    	q.pop();

    	if(b >= p){
    		if(b - p == e){
    			cout<<v + 1;
    			return 0;
    		}

    		int w = hasher((b - p) * N + p);

    		if(calc[w] == 0){
    			insert(b - p, v + 1);
    			if(calc[w] == 0){
    				q.push({(b - p) * N  + p, v + 1});
    				calc[w] = 1;
    			}
    		}
    	}
    	if(b + p < n){
    		if(b + p == e){
    			cout<<v + 1;
    			return 0;
    		}

    		int w = hasher((b + p) * N + p);

    		if(calc[w] == 0){
    			insert(b + p, v + 1);
    			if(calc[w] == 0){
    				q.push({(b + p) * N  + p, v + 1});
    				calc[w] = 1;
    			}
    		}
    	}
    }
    cout<<-1;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:7: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if(b - p == e){
       ^~
skyscraper.cpp:41:15: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int n, m, s, e;
               ^

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