Submission #970652

#	Time	Username	Problem	Language	Result	Execution time	Memory
970652		PenguinsAreCute	Passport (JOI23_passport)	C++17	0 / 100	4 ms	9820 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define hello cout<<"line "<<__LINE__<<endl;
#define hello 69
using ii = pair<int,int>;
vector<ii> adj[400005];
void bfs(int s, int dist[]) {
	dist[s] = 0;
	priority_queue<ii,vector<ii>,greater<ii>> pq;
	for(pq.push({0,s});pq.size();) {
		auto [d,x] = pq.top(); pq.pop();
		if(d!=dist[x]) continue;
		for(auto [i,di]: adj[x]) if(dist[i]>d+di) {
			dist[i] = d+di;
			pq.push({d+di,i});
		}
	}
}
main() {
	int n; cin >> n;
	int l[n], r[n]; for(int i=0;i<n;i++) {cin>>l[i]>>r[i]; l[i]--;}
	for(int i=1;i<n;i++) {adj[i<<1].push_back({i,0}); adj[i<<1|1].push_back({i,0});}
	for(int i=0;i<n;i++) {
		for(int ll=l[i]+n,rr=r[i]+n;ll<rr;ll>>=1,rr>>=1) {
			if(ll&1) adj[ll++].push_back({i+n,1});
			if(rr&1) adj[--rr].push_back({i+n,1});
		}
	}
	int dista[2*n], distb[2*n], distt[2*n+5];
	fill(dista,dista+2*n,12102010);
	fill(distb,distb+2*n,12102010);
	fill(distt,distt+2*n+5,12102010);
	bfs(n,dista);
	bfs(2*n-1,distb);
	for(int i=0;i<n;i++) adj[2*n].push_back({i+n,dista[i+n]+distb[i+n]});
	bfs(2*n,distt);
	int q; cin >> q; for(int x;q--;) {
		cin >> x;
		cout << (distt[x]==12102010?-1:distt[x]+1) << "\n";
	}
}

Compilation message (stderr)

passport.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main() {
      | ^~~~

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