Submission #783345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783345	2023-07-14T21:13:13 Z	fuad27	Passport (JOI23_passport)	C++17	100 / 100	317 ms	20728 KB

passport

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int INF=1e9+10;
struct pass {
	int l, r, i;
};
int n;
struct ST {
	vector<int> mx;
	vector<pass> p;
	int n=1;
	ST(vector<pass> v) {
		while(n<(int)v.size()) {
			n*=2;
		}
		p=v;
		mx.resize(2*n,-1);
		for(int i = 0;i<(int)v.size();i++) {
			mx[i+n]=v[i].r;
		}
		for(int i = n-1;i>=0;i--)mx[i]=max(mx[2*i], mx[2*i+1]);
	}
	void get(vector<int>&a, int idx, int v=1, int l=0, int r=-1) {
		if(r<0)r+=n;	
		if(l>=(int)p.size() or p[l].l>idx or mx[v]<idx) {
			return;
		}
		else if(l==r){
			a.push_back(l);
			mx[v]=-1;
			return;
		}
		else {
			int tm=(l+r)/2;
			get(a,idx,2*v,l,tm);
			get(a,idx,2*v+1,tm+1,r);
			mx[v]=max(mx[2*v],mx[2*v+1]);
		}
	}
};
vector<pass> p;
// [0,n-1] -> country
// [n,2n-1] -> passport
void dijkstra(vector<int> &dist) {
	ST s(p);
	for(int i = n;i<2*n;i++) {
		dist[p[i-n].i]=min(dist[p[i-n].i], dist[i]+1);
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;
	for(int i = 0;i<n;i++)pq.push({dist[i],i});
	while(pq.size()) {
		auto at=pq.top();
		pq.pop();
		if(at.first>dist[at.second])continue;
		vector<int> cc;
		s.get(cc,at.second);
		for(auto i:cc) {
			if(dist[i+n]>at.first) {
				dist[i+n]=at.first;
				if(dist[p[i].i]>dist[i+n]+1) {
					dist[p[i].i]=dist[i+n]+1;
					pq.push({dist[p[i].i], p[i].i});
				}
			}
		}
	}
}
int main () {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	p.resize(n);
	for(int i = 0;i<n;i++){
		cin >> p[i].l >> p[i].r;
		p[i].l--,p[i].r--;
		p[i].i=i;
	}
	sort(p.begin(),p.end(), [](const pass &A, const pass &B) {
		return A.l<B.l;
	});
	vector<int> dl(n+n, INF), dr(n+n,INF);	
	dl[0]=0, dr[n-1]=0;
	dijkstra(dl);
	dijkstra(dr);
	vector<int> d(n+n);
	for(int i = 0;i<2*n;i++) {
		d[i]=dl[i]+dr[i];
	}
	dijkstra(d);
	int q;
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		if(d[x-1]>=INF)d[x-1]=-1;
		cout << d[x-1] << "\n";
	}
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	281 ms	19200 KB	Output is correct
5	Correct	257 ms	17984 KB	Output is correct
6	Correct	229 ms	18204 KB	Output is correct
7	Correct	133 ms	19048 KB	Output is correct
8	Correct	106 ms	15468 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct

Subtask #3
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	3 ms	456 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	560 KB	Output is correct
19	Correct	3 ms	504 KB	Output is correct
20	Correct	3 ms	468 KB	Output is correct
21	Correct	4 ms	468 KB	Output is correct
22	Correct	2 ms	460 KB	Output is correct
23	Correct	4 ms	544 KB	Output is correct
24	Correct	4 ms	468 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	3 ms	456 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	560 KB	Output is correct
19	Correct	3 ms	504 KB	Output is correct
20	Correct	3 ms	468 KB	Output is correct
21	Correct	4 ms	468 KB	Output is correct
22	Correct	2 ms	460 KB	Output is correct
23	Correct	4 ms	544 KB	Output is correct
24	Correct	4 ms	468 KB	Output is correct
25	Correct	1 ms	320 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	5 ms	556 KB	Output is correct
28	Correct	3 ms	468 KB	Output is correct
29	Correct	3 ms	584 KB	Output is correct
30	Correct	3 ms	568 KB	Output is correct
31	Correct	4 ms	468 KB	Output is correct

Subtask #5
46.0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	281 ms	19200 KB	Output is correct
5	Correct	257 ms	17984 KB	Output is correct
6	Correct	229 ms	18204 KB	Output is correct
7	Correct	133 ms	19048 KB	Output is correct
8	Correct	106 ms	15468 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	320 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	324 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	3 ms	456 KB	Output is correct
25	Correct	3 ms	468 KB	Output is correct
26	Correct	3 ms	560 KB	Output is correct
27	Correct	3 ms	504 KB	Output is correct
28	Correct	3 ms	468 KB	Output is correct
29	Correct	4 ms	468 KB	Output is correct
30	Correct	2 ms	460 KB	Output is correct
31	Correct	4 ms	544 KB	Output is correct
32	Correct	4 ms	468 KB	Output is correct
33	Correct	1 ms	320 KB	Output is correct
34	Correct	1 ms	320 KB	Output is correct
35	Correct	5 ms	556 KB	Output is correct
36	Correct	3 ms	468 KB	Output is correct
37	Correct	3 ms	584 KB	Output is correct
38	Correct	3 ms	568 KB	Output is correct
39	Correct	4 ms	468 KB	Output is correct
40	Correct	317 ms	20728 KB	Output is correct
41	Correct	258 ms	18344 KB	Output is correct
42	Correct	242 ms	18356 KB	Output is correct
43	Correct	216 ms	19500 KB	Output is correct
44	Correct	267 ms	18344 KB	Output is correct
45	Correct	281 ms	18324 KB	Output is correct
46	Correct	116 ms	7736 KB	Output is correct
47	Correct	229 ms	19436 KB	Output is correct
48	Correct	264 ms	19564 KB	Output is correct

Submission #783345

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 8.0 / 8.0

Subtask #5 46.0 / 46.0

Subtask #1
6.0 / 6.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
8.0 / 8.0

Subtask #5
46.0 / 46.0