Submission #1026779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026779		Unforgettablepl	Passport (JOI23_passport)	C++17	48 / 100	2062 ms	458704 KiB

passport

#pragma GCC optimize("Ofast","unroll-loops")
#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<pair<int,bool>>> adj(n+1);
	int S = n;
	vector<vector<int>> lift(n+1,vector<int>(18));
	// Do the binary lift magic
	for(int i=1;i<=n;i++)lift[i][0]=i;
	for(int bit=1;bit<18;bit++){
		for(int i=1;i<=n;i++){
			lift[i][bit]=++S;
			adj.emplace_back();
			adj[lift[i][bit-1]].emplace_back(S,false);
			adj[lift[max(0ll,i-(1<<(bit-1)))][bit-1]].emplace_back(S,false);
		}
	}
	vector<pair<int,int>> ranges(n+1);
	for(int i=1;i<=n;i++){
		int l,r;cin>>l>>r;
		ranges[i]={l,r};
		int tar = r-l+1;
		for(int bit=0;bit<18;bit++)if(tar&(1<<bit)){
			adj[lift[r][bit]].emplace_back(i,true);
			r-=(1<<bit);
		}
	}
	vector<int> distL(S+1,INF);
	vector<int> distR(S+1,INF);
	{
		// distL calculation
		deque<pair<int,int>> q;
		for(int i=1;i<=n;i++){
			if(ranges[i].first==1)q.emplace_back(i,0);
		}
		vector<bool> visited(S+1);
		while(!q.empty()){
			auto [idx,dist] = q.front();q.pop_front();
			if(visited[idx])continue;
			visited[idx]=true;
			distL[idx]=dist;
			for(auto&[i,type]:adj[idx])if(!visited[i])
				if(type)q.emplace_back(i,dist+1);
				else q.emplace_front(i,dist);
		}
	}
	{
		// distR calculation
		deque<pair<int,int>> q;
		for(int i=1;i<=n;i++){
			if(ranges[i].second==n)q.emplace_back(i,0);
		}
		vector<bool> visited(S+1);
		while(!q.empty()){
			auto [idx,dist] = q.front();q.pop_front();
			if(visited[idx])continue;
			visited[idx]=true;
			distR[idx]=dist;
			for(auto&[i,type]:adj[idx])if(!visited[i])
				if(type)q.emplace_back(i,dist+1);
				else q.emplace_front(i,dist);
		}
	}
	vector<int> totdist(S+1,INF);
	{
		// totdist calculation
		vector<bool> visited(S+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(auto&[i,type]:adj[idx])if(!visited[i])
				if(type)q.emplace(-dist-1,i);
				else q.emplace(-dist,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';
	}
}

Compilation message (stderr)

passport.cpp: In function 'int32_t main()':
passport.cpp:51:33: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   51 |    for(auto&[i,type]:adj[idx])if(!visited[i])
      |                                 ^
passport.cpp:68:33: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   68 |    for(auto&[i,type]:adj[idx])if(!visited[i])
      |                                 ^
passport.cpp:86:33: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   86 |    for(auto&[i,type]:adj[idx])if(!visited[i])
      |                                 ^

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