Submission #979677

#	Time	Username	Problem	Language	Result	Execution time	Memory
979677		temporary1	Passport (JOI23_passport)	C++17	100 / 100	624 ms	78876 KiB

passport

#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
 
vector<pair<int,int>> graph[800001];
int dist[3][800001];
int node[200001];

int max1 = 0;

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

int build(int n, int a, int b) {
	if (a == b) {
		max1 = max(max1,n);
		return node[a] = n;
	}
	graph[build(2*n,a,(a+b)/2)].push_back({n,0});
	graph[build(2*n+1,(a+b)/2+1,b)].push_back({n,0});
	return n;
}
 
void upd(int n, int a, int b, int x, int y, int k) {
	if (a > b || b < x || y < a)return;
	if (x <= a && b <= y) {
		graph[n].push_back({k,1});
		return;
	}
	upd(2*n,a,(a+b)/2,x,y,k);
	upd(2*n+1,(a+b)/2+1,b,x,y,k);
	return;
}

int main() {
	int n;
	scanf("%d",&n);
	build(1,1,n);
	for (int i = 1; i <= n; ++i) {
		int l, r;
		scanf("%d%d",&l,&r);
		upd(1,1,n,l,r,node[i]);
	}
	for (int i = 0; i < 3; ++i) {
		fill(dist[i]+1,dist[i]+max1+1,1e9);
		if (i == 0) {
			dist[0][node[1]] = 0;
			pq.push({0,node[1]});
		} else if (i == 1) {
			dist[1][node[n]] = 0;
			pq.push({0,node[n]});
		} else if (i == 2) {
			dist[0][node[1]] = 1;
			dist[1][node[n]] = 1;
			for (int j = 1; j <= n; ++j) {
				dist[2][node[j]] = dist[0][node[j]]+dist[1][node[j]]-1;
				pq.push({dist[2][node[j]],node[j]});
			}
		}
		while (pq.size()) {
			int d, x;
			tie(d,x) = pq.top();
			pq.pop();
			if (dist[i][x] < d)continue;
			for (auto it : graph[x]) {
				if (dist[i][it.f] > dist[i][x]+it.s) {
					dist[i][it.f] = dist[i][x]+it.s;
					pq.push({dist[i][it.f],it.f});
				}
			}
		}
	}
	int q;
	scanf("%d",&q);
	for (int qi = 0; qi < q; ++qi) {
		int x;
		scanf("%d",&x);
		if (dist[2][node[x]] > n)printf("-1\n");
		else printf("%d\n",dist[2][node[x]]);
	}
	return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
passport.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~
passport.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
passport.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

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