oj.uz

Submission #1011908

# Submission time Handle Problem Language Result Execution time Memory
1011908 2024-07-01T10:53:43 Z pcc Passport (JOI23_passport) C++17
100 / 100
 836 ms 213048 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
const int LEN = mxn*100;

int head[LEN],nid[LEN],to[LEN],wei[LEN];
int ecnt = 0,vcnt = 0;
int N,Q;

void add_edge(int a,int b){
	ecnt++;
	assert(ecnt<LEN);
	nid[ecnt] = head[a];
	head[a] = ecnt;
	to[ecnt] = b;
	return;
}

int newvertex(){
	return ++vcnt;
}

int seg[mxn*4];
pii arr[mxn];
int req[mxn];
int d1[LEN],d2[LEN];

void build(int now,int l,int r){
	if(l == r){
		seg[now] = l;
		return;
	}
	seg[now] = newvertex();
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	add_edge(seg[now*2+1],seg[now]);
	add_edge(seg[now*2+2],seg[now]);
}

void addseg(int now,int l,int r,int s,int e,int id){
	if(l>=s&&e>=r){
		add_edge(seg[now],id);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)addseg(now*2+1,l,mid,s,e,id);
	if(mid<e)addseg(now*2+2,mid+1,r,s,e,id);
	return;
}

namespace DIJKSTRA{
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	bitset<LEN> vis;
	void GO(int dist[]){
		vis.reset();
		for(int i = 1;i<=vcnt;i++)pq.push(pii(dist[i],i));
		while(!pq.empty()){
			auto [d,now] = pq.top();
			pq.pop();
			if(vis[now])continue;
			vis[now] = true;
			for(int eid = head[now];eid;eid = nid[eid]){
				int nxt = to[eid],w = wei[now];
				if(dist[nxt]>d+w){
					dist[nxt] = d+w;
					pq.push(pii(dist[nxt],nxt));
				}
			}
		}
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	vcnt = N;
	for(int i = 1;i<=N;i++)cin>>arr[i].fs>>arr[i].sc;
	cin>>Q;
	for(int i = 0;i<Q;i++)cin>>req[i];
	build(0,1,N);
	for(int i = 1;i<=N;i++){
		int id = newvertex();
		wei[id] = 1;
		addseg(0,1,N,arr[i].fs,arr[i].sc,id);
		add_edge(id,i);
	}
	fill(d1,d1+LEN,LEN);
	fill(d2,d2+LEN,LEN);
	d1[1] = d2[N] = 0;
	DIJKSTRA::GO(d1);
	DIJKSTRA::GO(d2);
	for(int i = 1;i<=vcnt;i++)d1[i] += d2[i];
	DIJKSTRA::GO(d1);
	for(int i = 0;i<Q;i++){
		auto re = d1[req[i]];
		cout<<(re>mxn?-1:re)<<'\n';
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 168804 KB Output is correct
2 Correct 65 ms 168788 KB Output is correct
3 Correct 66 ms 168664 KB Output is correct
4 Correct 836 ms 206276 KB Output is correct
5 Correct 443 ms 191784 KB Output is correct
6 Correct 414 ms 188724 KB Output is correct
7 Correct 383 ms 186052 KB Output is correct
8 Correct 271 ms 193736 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 168664 KB Output is correct
2 Correct 66 ms 168792 KB Output is correct
3 Correct 67 ms 168788 KB Output is correct
4 Correct 86 ms 168788 KB Output is correct
5 Correct 65 ms 168788 KB Output is correct
6 Correct 76 ms 168812 KB Output is correct
7 Correct 82 ms 168784 KB Output is correct
8 Correct 66 ms 168828 KB Output is correct
9 Correct 68 ms 168680 KB Output is correct
10 Correct 79 ms 168728 KB Output is correct
11 Correct 77 ms 168880 KB Output is correct
12 Correct 74 ms 168732 KB Output is correct
13 Correct 73 ms 168788 KB Output is correct
14 Correct 62 ms 168736 KB Output is correct
15 Correct 66 ms 168788 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 168664 KB Output is correct
2 Correct 66 ms 168792 KB Output is correct
3 Correct 67 ms 168788 KB Output is correct
4 Correct 86 ms 168788 KB Output is correct
5 Correct 65 ms 168788 KB Output is correct
6 Correct 76 ms 168812 KB Output is correct
7 Correct 82 ms 168784 KB Output is correct
8 Correct 66 ms 168828 KB Output is correct
9 Correct 68 ms 168680 KB Output is correct
10 Correct 79 ms 168728 KB Output is correct
11 Correct 77 ms 168880 KB Output is correct
12 Correct 74 ms 168732 KB Output is correct
13 Correct 73 ms 168788 KB Output is correct
14 Correct 62 ms 168736 KB Output is correct
15 Correct 66 ms 168788 KB Output is correct
16 Correct 75 ms 169044 KB Output is correct
17 Correct 67 ms 169044 KB Output is correct
18 Correct 109 ms 169044 KB Output is correct
19 Correct 68 ms 168872 KB Output is correct
20 Correct 69 ms 169044 KB Output is correct
21 Correct 70 ms 169044 KB Output is correct
22 Correct 72 ms 169040 KB Output is correct
23 Correct 63 ms 169048 KB Output is correct
24 Correct 69 ms 169040 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 168664 KB Output is correct
2 Correct 66 ms 168792 KB Output is correct
3 Correct 67 ms 168788 KB Output is correct
4 Correct 86 ms 168788 KB Output is correct
5 Correct 65 ms 168788 KB Output is correct
6 Correct 76 ms 168812 KB Output is correct
7 Correct 82 ms 168784 KB Output is correct
8 Correct 66 ms 168828 KB Output is correct
9 Correct 68 ms 168680 KB Output is correct
10 Correct 79 ms 168728 KB Output is correct
11 Correct 77 ms 168880 KB Output is correct
12 Correct 74 ms 168732 KB Output is correct
13 Correct 73 ms 168788 KB Output is correct
14 Correct 62 ms 168736 KB Output is correct
15 Correct 66 ms 168788 KB Output is correct
16 Correct 75 ms 169044 KB Output is correct
17 Correct 67 ms 169044 KB Output is correct
18 Correct 109 ms 169044 KB Output is correct
19 Correct 68 ms 168872 KB Output is correct
20 Correct 69 ms 169044 KB Output is correct
21 Correct 70 ms 169044 KB Output is correct
22 Correct 72 ms 169040 KB Output is correct
23 Correct 63 ms 169048 KB Output is correct
24 Correct 69 ms 169040 KB Output is correct
25 Correct 72 ms 168788 KB Output is correct
26 Correct 69 ms 168748 KB Output is correct
27 Correct 68 ms 167036 KB Output is correct
28 Correct 68 ms 165064 KB Output is correct
29 Correct 66 ms 164948 KB Output is correct
30 Correct 69 ms 169044 KB Output is correct
31 Correct 62 ms 169040 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 168804 KB Output is correct
2 Correct 65 ms 168788 KB Output is correct
3 Correct 66 ms 168664 KB Output is correct
4 Correct 836 ms 206276 KB Output is correct
5 Correct 443 ms 191784 KB Output is correct
6 Correct 414 ms 188724 KB Output is correct
7 Correct 383 ms 186052 KB Output is correct
8 Correct 271 ms 193736 KB Output is correct
9 Correct 66 ms 168664 KB Output is correct
10 Correct 66 ms 168792 KB Output is correct
11 Correct 67 ms 168788 KB Output is correct
12 Correct 86 ms 168788 KB Output is correct
13 Correct 65 ms 168788 KB Output is correct
14 Correct 76 ms 168812 KB Output is correct
15 Correct 82 ms 168784 KB Output is correct
16 Correct 66 ms 168828 KB Output is correct
17 Correct 68 ms 168680 KB Output is correct
18 Correct 79 ms 168728 KB Output is correct
19 Correct 77 ms 168880 KB Output is correct
20 Correct 74 ms 168732 KB Output is correct
21 Correct 73 ms 168788 KB Output is correct
22 Correct 62 ms 168736 KB Output is correct
23 Correct 66 ms 168788 KB Output is correct
24 Correct 75 ms 169044 KB Output is correct
25 Correct 67 ms 169044 KB Output is correct
26 Correct 109 ms 169044 KB Output is correct
27 Correct 68 ms 168872 KB Output is correct
28 Correct 69 ms 169044 KB Output is correct
29 Correct 70 ms 169044 KB Output is correct
30 Correct 72 ms 169040 KB Output is correct
31 Correct 63 ms 169048 KB Output is correct
32 Correct 69 ms 169040 KB Output is correct
33 Correct 72 ms 168788 KB Output is correct
34 Correct 69 ms 168748 KB Output is correct
35 Correct 68 ms 167036 KB Output is correct
36 Correct 68 ms 165064 KB Output is correct
37 Correct 66 ms 164948 KB Output is correct
38 Correct 69 ms 169044 KB Output is correct
39 Correct 62 ms 169040 KB Output is correct
40 Correct 704 ms 207816 KB Output is correct
41 Correct 430 ms 193224 KB Output is correct
42 Correct 482 ms 213048 KB Output is correct
43 Correct 499 ms 213036 KB Output is correct
44 Correct 366 ms 189904 KB Output is correct
45 Correct 386 ms 194820 KB Output is correct
46 Correct 174 ms 174792 KB Output is correct
47 Correct 382 ms 195948 KB Output is correct
48 Correct 420 ms 201268 KB Output is correct