Submission #1304949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304949		vlomaczk	Passport (JOI23_passport)	C++20	100 / 100	658 ms	158236 KiB

passport

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

ll base = 1<<18;
ll inf = 1e9;
ll n;
vector<vector<pair<ll, ll>>> gt(3*base);

vector<ll> bfs(ll s) {
	vector<ll> dist(3*base, inf);
	dist[s] = 0;
	deque<ll> Q;
	Q.push_front(s);
	while(Q.size()) {
		ll v = Q.front(); Q.pop_front();
		for(auto[u,c] : gt[v]) {
			if(c==0) {
				if(dist[u]==inf) {
					dist[u] = dist[v];
					Q.push_front(u);
				}
			} else {
				if(dist[u]==inf) {
					dist[u] = dist[v] + 1;
					Q.push_back(u);
				}
			}
		}
	}
	return dist;
}

void dijkstra(vector<ll> &dist) {
	priority_queue<pair<int, int>> pq;
	for(int i=1; i<3*base; ++i) pq.push({-dist[i], i});
	while(pq.size()) {
		auto[dv, v] = pq.top();
		pq.pop(); dv*=-1;
		if(dist[v] != dv) continue;
		for(auto[u, c] : gt[v]) {
			if(dist[u] > dist[v] + c) {
				dist[u] = dist[v] + c;
				pq.push({-dist[u], u});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int cnt = 2*base;
	cin >> n;
	for(ll i=1; i<=n; ++i) {
		ll l, r;
		cin >> l >> r;
		if(l==r) continue;
		l += base-1;
		r += base+1;
		gt[cnt].push_back({i+base,1});
		while(l/2 != r/2) {
			if(l%2==0) {
				gt[l+1].push_back({cnt,0});
			}
			if(r%2==1) {
				gt[r-1].push_back({cnt,0});
			}
			l/=2; r/=2;
		}
		++cnt;
	}
	

	for(ll i=1; i<base; ++i) {
		gt[i+i].push_back({i, 0});
		gt[i+i+1].push_back({i, 0});
	}

	vector<ll> d1 = bfs(1+base);
	vector<ll> dN = bfs(n+base);
	vector<ll> dist(3*base);
	for(ll i=1; i<3*base; ++i) dist[i] = d1[i] + dN[i];
	dijkstra(dist);
	ll q; cin >> q;
	while(q--) {
		ll x; cin >> x;
		x += base;
		if(dist[x] >= inf) cout << "-1\n";
		else cout << dist[x] << "\n";
	}

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46