Submission #160946

#	Time	Username	Problem	Language	Result	Execution time	Memory
160946		nvmdava	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	622 ms	216968 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];
 
queue<pair<int, int> > q;
 
int pri, r1, r2;

inline int binpow(int a, int b){
	int s = 1;
	while(b){
		if(b & 1){
			s = 1LL * s * a % pri;
		}
		a = 1LL * a * a % pri;
		b >>= 1;
	}
	return s;
}

inline int hasher(int b, int p){
	return  binpow(p * N + 1, b + 1);
}
void insert(int s, int v){
	if(in[s]) return;
	in[s] = 1;
 
	for(auto x : pl[s]){
		int w = hasher(s, 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;
 
    vector<int> asd = {220000871, 220002131, 220002631, 220002397};
    pri = asd[rng() % 4];
 	r1 = rng() % pri;
 	r2 = rng() % pri;
    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, 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, 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:80:7: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
       if(b - p == e){
       ^~
skyscraper.cpp:52: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