답안 #744695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744695	2023-05-19T02:18:46 Z	emptypringlescan	Passport (JOI23_passport)	C++17	100 / 100	1269 ms	145780 KB

passport

#include <bits/stdc++.h>
using namespace std;
int cnd;
vector<pair<int,int> > adj[800005];
struct node{
	int s,e,m;
	int nd;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		nd=cnd;
		cnd++;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			adj[l->nd].push_back({nd,0});
			adj[r->nd].push_back({nd,0});
		}
		else{
			adj[s].push_back({nd,0});
		}
	}
	void addedge(int S, int E, int N){
		if(S<=s&&e<=E){
			adj[nd].push_back({N,1});
			return;
		}
		if(E<=m) l->addedge(S,E,N);
		else if(S>m) r->addedge(S,E,N);
		else{
			l->addedge(S,m,N);
			r->addedge(m+1,E,N);
		}
	}
} *root;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	cnd=n+1;
	root = new node(1,n);
	deque<pair<int,pair<int,int> > > dq;
	priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > pq;
	int dist[cnd][3];
	memset(dist,-1,sizeof(dist));
	for(int i=0; i<n; i++){
		int a,b;
		cin >> a >> b;
		root->addedge(a,b,i+1);
		if(a==1) dq.push_back({1,{1,i+1}});
		if(b==n) dq.push_back({1,{2,i+1}});
	}
	while(!dq.empty()){
		int a=dq.front().first,b=dq.front().second.first,c=dq.front().second.second;
		dq.pop_front();
		if(dist[c][b]!=-1) continue;
		dist[c][b]=a;
		for(auto i:adj[c]){
			if(dist[i.first][b]==-1){
				if(i.second==1) dq.push_back({a+i.second,{b,i.first}});
				else dq.push_front({a+i.second,{b,i.first}});
			}
		}
	}
	for(int i=1; i<=n; i++){
		//cout << dist[i][1] << ' ' << dist[i][2] << '\n';
		if(dist[i][1]!=-1&&dist[i][2]!=-1){
			pq.push({dist[i][1]+dist[i][2]-1,{0,i}});
		}
	}
	while(!pq.empty()){
		int a=pq.top().first,b=pq.top().second.first,c=pq.top().second.second;
		pq.pop();
		if(dist[c][b]!=-1) continue;
		dist[c][b]=a;
		for(auto i:adj[c]){
			if(dist[i.first][b]==-1) pq.push({a+i.second,{b,i.first}});
		}
	}
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		int x;
		cin >> x;
		cout << dist[x][0] << '\n';
	}
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19028 KB	Output is correct
2	Correct	11 ms	19028 KB	Output is correct
3	Correct	10 ms	18996 KB	Output is correct
4	Correct	1198 ms	145780 KB	Output is correct
5	Correct	447 ms	75672 KB	Output is correct
6	Correct	260 ms	69956 KB	Output is correct
7	Correct	214 ms	73588 KB	Output is correct
8	Correct	140 ms	69960 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19100 KB	Output is correct
2	Correct	11 ms	19004 KB	Output is correct
3	Correct	10 ms	19028 KB	Output is correct
4	Correct	11 ms	19108 KB	Output is correct
5	Correct	10 ms	19104 KB	Output is correct
6	Correct	10 ms	19064 KB	Output is correct
7	Correct	11 ms	19028 KB	Output is correct
8	Correct	11 ms	19064 KB	Output is correct
9	Correct	10 ms	19036 KB	Output is correct
10	Correct	10 ms	19028 KB	Output is correct
11	Correct	11 ms	19224 KB	Output is correct
12	Correct	11 ms	19184 KB	Output is correct
13	Correct	11 ms	19156 KB	Output is correct
14	Correct	11 ms	19188 KB	Output is correct
15	Correct	11 ms	19084 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19100 KB	Output is correct
2	Correct	11 ms	19004 KB	Output is correct
3	Correct	10 ms	19028 KB	Output is correct
4	Correct	11 ms	19108 KB	Output is correct
5	Correct	10 ms	19104 KB	Output is correct
6	Correct	10 ms	19064 KB	Output is correct
7	Correct	11 ms	19028 KB	Output is correct
8	Correct	11 ms	19064 KB	Output is correct
9	Correct	10 ms	19036 KB	Output is correct
10	Correct	10 ms	19028 KB	Output is correct
11	Correct	11 ms	19224 KB	Output is correct
12	Correct	11 ms	19184 KB	Output is correct
13	Correct	11 ms	19156 KB	Output is correct
14	Correct	11 ms	19188 KB	Output is correct
15	Correct	11 ms	19084 KB	Output is correct
16	Correct	16 ms	20204 KB	Output is correct
17	Correct	14 ms	19796 KB	Output is correct
18	Correct	15 ms	20052 KB	Output is correct
19	Correct	15 ms	20064 KB	Output is correct
20	Correct	13 ms	19744 KB	Output is correct
21	Correct	13 ms	19804 KB	Output is correct
22	Correct	12 ms	19668 KB	Output is correct
23	Correct	14 ms	19924 KB	Output is correct
24	Correct	13 ms	19876 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19100 KB	Output is correct
2	Correct	11 ms	19004 KB	Output is correct
3	Correct	10 ms	19028 KB	Output is correct
4	Correct	11 ms	19108 KB	Output is correct
5	Correct	10 ms	19104 KB	Output is correct
6	Correct	10 ms	19064 KB	Output is correct
7	Correct	11 ms	19028 KB	Output is correct
8	Correct	11 ms	19064 KB	Output is correct
9	Correct	10 ms	19036 KB	Output is correct
10	Correct	10 ms	19028 KB	Output is correct
11	Correct	11 ms	19224 KB	Output is correct
12	Correct	11 ms	19184 KB	Output is correct
13	Correct	11 ms	19156 KB	Output is correct
14	Correct	11 ms	19188 KB	Output is correct
15	Correct	11 ms	19084 KB	Output is correct
16	Correct	16 ms	20204 KB	Output is correct
17	Correct	14 ms	19796 KB	Output is correct
18	Correct	15 ms	20052 KB	Output is correct
19	Correct	15 ms	20064 KB	Output is correct
20	Correct	13 ms	19744 KB	Output is correct
21	Correct	13 ms	19804 KB	Output is correct
22	Correct	12 ms	19668 KB	Output is correct
23	Correct	14 ms	19924 KB	Output is correct
24	Correct	13 ms	19876 KB	Output is correct
25	Correct	10 ms	19028 KB	Output is correct
26	Correct	10 ms	19076 KB	Output is correct
27	Correct	17 ms	20180 KB	Output is correct
28	Correct	15 ms	19796 KB	Output is correct
29	Correct	14 ms	19808 KB	Output is correct
30	Correct	13 ms	19732 KB	Output is correct
31	Correct	14 ms	19896 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19028 KB	Output is correct
2	Correct	11 ms	19028 KB	Output is correct
3	Correct	10 ms	18996 KB	Output is correct
4	Correct	1198 ms	145780 KB	Output is correct
5	Correct	447 ms	75672 KB	Output is correct
6	Correct	260 ms	69956 KB	Output is correct
7	Correct	214 ms	73588 KB	Output is correct
8	Correct	140 ms	69960 KB	Output is correct
9	Correct	11 ms	19100 KB	Output is correct
10	Correct	11 ms	19004 KB	Output is correct
11	Correct	10 ms	19028 KB	Output is correct
12	Correct	11 ms	19108 KB	Output is correct
13	Correct	10 ms	19104 KB	Output is correct
14	Correct	10 ms	19064 KB	Output is correct
15	Correct	11 ms	19028 KB	Output is correct
16	Correct	11 ms	19064 KB	Output is correct
17	Correct	10 ms	19036 KB	Output is correct
18	Correct	10 ms	19028 KB	Output is correct
19	Correct	11 ms	19224 KB	Output is correct
20	Correct	11 ms	19184 KB	Output is correct
21	Correct	11 ms	19156 KB	Output is correct
22	Correct	11 ms	19188 KB	Output is correct
23	Correct	11 ms	19084 KB	Output is correct
24	Correct	16 ms	20204 KB	Output is correct
25	Correct	14 ms	19796 KB	Output is correct
26	Correct	15 ms	20052 KB	Output is correct
27	Correct	15 ms	20064 KB	Output is correct
28	Correct	13 ms	19744 KB	Output is correct
29	Correct	13 ms	19804 KB	Output is correct
30	Correct	12 ms	19668 KB	Output is correct
31	Correct	14 ms	19924 KB	Output is correct
32	Correct	13 ms	19876 KB	Output is correct
33	Correct	10 ms	19028 KB	Output is correct
34	Correct	10 ms	19076 KB	Output is correct
35	Correct	17 ms	20180 KB	Output is correct
36	Correct	15 ms	19796 KB	Output is correct
37	Correct	14 ms	19808 KB	Output is correct
38	Correct	13 ms	19732 KB	Output is correct
39	Correct	14 ms	19896 KB	Output is correct
40	Correct	1269 ms	144772 KB	Output is correct
41	Correct	485 ms	78336 KB	Output is correct
42	Correct	525 ms	105444 KB	Output is correct
43	Correct	534 ms	116272 KB	Output is correct
44	Correct	306 ms	72288 KB	Output is correct
45	Correct	299 ms	78800 KB	Output is correct
46	Correct	159 ms	43980 KB	Output is correct
47	Correct	464 ms	89536 KB	Output is correct
48	Correct	454 ms	92680 KB	Output is correct

답안 #744695

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