제출 #281807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281807		nvmdava	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	215 ms	217048 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;
int o = rng() % 5000000;
int hasher(int b, int p){
	int a = p * N + b;
	a ^= o;
	return 1LL * a * a % pri;
}
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];
 
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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