Submission #1026758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026758		Unforgettablepl	Passport (JOI23_passport)	C++17	48 / 100	1207 ms	1048580 KiB

passport

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

#define int long long

const int INF = 1e15;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	vector<pair<int,int>> ranges(n+1);
	for(int i=1;i<=n;i++){
		int l,r;cin>>l>>r;
		ranges[i]={l,r};
		for(int j=l;j<=r;j++)adj[j].emplace_back(i);
	}
	vector<int> distL(n+1,INF);
	vector<int> distR(n+1,INF);
	{
		// distL calculation
		queue<pair<int,int>> q;
		for(int i=1;i<=n;i++){
			if(ranges[i].first==1)q.emplace(i,0);
		}
		vector<bool> visited(n+1);
		while(!q.empty()){
			auto [idx,dist] = q.front();q.pop();
			if(visited[idx])continue;
			visited[idx]=true;
			distL[idx]=dist;
			for(int&i:adj[idx])if(!visited[i])q.emplace(i,dist+1);
		}
	}
	{
		// distR calculation
		queue<pair<int,int>> q;
		for(int i=1;i<=n;i++){
			if(ranges[i].second==n)q.emplace(i,0);
		}
		vector<bool> visited(n+1);
		while(!q.empty()){
			auto [idx,dist] = q.front();q.pop();
			if(visited[idx])continue;
			visited[idx]=true;
			distR[idx]=dist;
			for(int&i:adj[idx])if(!visited[i])q.emplace(i,dist+1);
		}
	}
	vector<int> totdist(n+1,INF);
	{
		// totdist calculation
		vector<bool> visited(n+1);
		priority_queue<pair<int,int>> q;
		for(int i=1;i<=n;i++){
			q.emplace(-(distL[i]+distR[i]+1),i);
		}
		while(!q.empty()){
			auto [dist,idx] = q.top();q.pop();dist=-dist;
			if(visited[idx])continue;
			visited[idx]=true;
			totdist[idx]=dist;
			for(int&i:adj[idx])if(!visited[i])q.emplace(-dist-1,i);
		}
	}
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int x;cin>>x;
		if(totdist[x]>=INF)cout<<"-1\n";
		else cout << totdist[x] << '\n';
	}
}

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