제출 #1362525

#제출 시각아이디문제언어결과실행 시간메모리
1362525Jawad_Akbar_JJPassport (JOI23_passport)C++20
16 / 100
1 ms580 KiB
#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int N = 1<<10;
vector<pair<int, int>> nei[N<<1];
int dst[3][N<<1];

void dijkstra(int D[]){
	set<pair<int, int>> st;
	for (int i=1;i<N+N;i++)
		st.insert({D[i], i});

	while (st.size() > 0){
		auto [mn, u] = *begin(st);
		st.erase(begin(st));

		if (D[u] != mn)
			continue;

		for (auto [i, w] : nei[u]){
			if (D[u] + w < D[i]){
				D[i] = D[u] + w;
				st.insert({D[i], i});
			}
		}
	}
}

int main(){
	int n, q;
	cin>>n;

	for (int i=N+N-1; i; i--){
		dst[0][i] = dst[1][i] = N;

		nei[i].push_back({i / 2, 0});
	}

	for (int i=1;i<=n;i++){
		int l, r;
		cin>>l>>r;
		dst[2][i+N] -= (1 < i and i < n);


		for (l += N-1, r += N+1; l + 1 < r; l /= 2, r /= 2){
			if (!(l & 1))
				nei[l^1].push_back({i + N, 1});//, cout<<i + N<<' '<<(l ^ 1)<<endl;
			if (r & 1)
				nei[r^1].push_back({i + N, 1});//, cout<<i + N<<' '<<(r ^ 1)<<endl;
		}
	}



	dst[0][N+1] = dst[1][N+n] = 0;
	dijkstra(dst[0]);
	dijkstra(dst[1]);

	for (int i=1;i<N+N;i++){
		dst[2][i] += dst[0][i] + dst[1][i];
		// cout<<i<<' '<<dst[0][i]<<' '<<dst[1][i]<<' '<<dst[2][i]<<endl;

	}
	dijkstra(dst[2]);


	cin>>q;
	for (int i=1, x;i<=q;i++){
		cin>>x;
		cout<<(dst[2][x + N] >= N ? -1 : dst[2][x + N])<<endl;
	}
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…