Submission #1183994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183994		KK_1729	Passport (JOI23_passport)	C++20	100 / 100	930 ms	135904 KiB

passport

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}

struct Graph{
	vector<vector<pair<int, int>>> adj;
	vector<int> visited;
	// vector<int> dist;

	int N;
	Graph(int n){
		adj.resize(n+1);
		visited.resize(n+1);
		// dist.resize(n+1, 1e17);
		this->N = n;
	}

	void a(int u, int v, int w){
		adj[u].pb({v, w});
	}

	vector<int> dijkstra(int start){
		using T = pair<long long, int>;
		priority_queue<T, vector<T>, greater<T>> pq;
		vector<int> dist(N+1, 1e12);
		dist[start] = 0; 

		pq.push({0, start});
		while (!pq.empty()) {

			const auto [cdist, node] = pq.top();
			pq.pop();
			if (cdist != dist[node]) { continue; }
			for (const pair<int, int> &i : adj[node]) {
				if (cdist + i.second < dist[i.first]) {
					pq.push({dist[i.first] = cdist + i.second, i.first});
				}
			}
		}
		return dist;
	}
};
void solve(){
	int n; cin >> n;
	vector<pair<int, int>> intervals;
	vector<int> candid;
	FOR(i,0,n){
		int l, r; cin >> l >> r;

		intervals.pb({l, r});
		if (l == 1 && r == n) candid.pb(i+1);
	}

	int N = n;
	while (__builtin_popcount(N) != 1) N++;
	Graph g(2*N+1);

	FOR(i,1,N){

		g.a(2*i, i, 0);
		g.a(2*i+1, i, 0);
	}

	FOR(i,1,n+1){
		int l = intervals[i-1].first;
		int r = intervals[i-1].second;
		stack<vector<int>> s;
		s.push({1, N, l, r, 1});
		while (!s.empty()){
			vector<int> x = s.top();
			s.pop();
			if (x[0] > x[3] || x[1] < x[2]) continue;

			if (x[0] >= x[2] && x[1] <= x[3]){
				g.a(x[4], i+N-1, 1);
				continue;
			}
			int mid = (x[0]+x[1])/2;
			s.push({x[0], mid, l, r, 2*x[4]});
			s.push({mid+1, x[1], l, r, 2*x[4]+1});
		}
	}
	// FOR(i,0,2*N){
	// 	for (auto x: g.adj[i]){
	// 		cout << i << " " << x.first << " " << x.second << endl;
	// 	}
	// }
	vector<int> dist1 = g.dijkstra(N);
	vector<int> distn = g.dijkstra(N+n-1);
	dist1[N] = 1;
	distn[N+n-1] = 1;
	// printVector(dist1);
	// cout << N+n-1 << endl;
	FOR(i,1,N+1){
		g.a(2*N, i+N-1, dist1[i+N-1]+distn[i+N-1]);

	}

	vector<int> distans = g.dijkstra(2*N);
	int q; cin >> q;
	while (q--){
		int x; cin >> x;

		if (distans[x+N-1] > 1e10){
			cout << -1 << endl;
		}else{
			cout << distans[x+N-1]-1 << endl;
		}
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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