oj.uz

Submission #1106705

# Submission time Handle Problem Language Result Execution time Memory
1106705 2024-10-30T23:30:13 Z inksamurai Passport (JOI23_passport) C++17
48 / 100
 1230 ms 1048576 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int) a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
#define _3M8yqhy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int inf=1e9;

void slv(){
	int n;
	cin>>n;

	vec(pii) a;
	rep(i,n){
		int l,r;
		cin>>l>>r;
		l-=1,r-=1;
		a.pb({l,r});
	}	

	vi pns(n,inf);
	// 12 way
	rep(t,2){
		vi d1(n,inf);
		{
			vec(vi) adj(n);
			rep(i,n){
				rng(j,a[i].fi,a[i].se+1){
					adj[j].pb(i);
				}
			}
			queue<int> que;
			rep(v,n){
				if(a[v].fi==0){
					d1[v]=1;
					que.push(v);
				}
			}
			while(sz(que)){
				int v=que.front();
				que.pop();
				for(auto u:adj[v]){
					if(d1[u]==inf){
						d1[u]=d1[v]+1;
						que.push(u);
					}
				}
			}
		}

		vi d12(n,inf);
		{
			vec(vi) adj(n);
			rep(i,n){
				rng(j,0,a[i].se+1){
					adj[j].pb(i);
				}
			}
			priority_queue<pii,vec(pii),greater<pii>> pq;
			rep(v,n){
				if(a[v].se==n-1){
					d12[v]=1;
					pq.push({d12[v],v});
				}
			}
			while(sz(pq)){
				auto [cosu,v]=pq.top();
				pq.pop();
				for(auto u:adj[v]){
					if(d12[u]>d12[v]+1){
						// if(u==n-1-3 and t==1) print(v,dp[v]);
						d12[u]=d12[v]+1;
						pq.push({d12[u],u});
					}
				}
			}
			rng(v,1,n-1){
				d12[v]+=d1[v]-1;
			}
			d12[n-1]=d1[n-1];
		}
		// if(t==1 and s==n-1-3) print("wtf",i,r,cnt);

		vi dp(n,inf);
		dp=d12;
		{
			vec(vi) adj(n);
			rep(i,n){
				rng(j,a[i].fi,a[i].se+1){
					adj[j].pb(i);
				}
			}
			priority_queue<pii,vec(pii),greater<pii>> pq;
			rep(v,n){
				pq.push({dp[v],v});
			}
			while(sz(pq)){
				auto [cosu,v]=pq.top();
				pq.pop();
				for(auto u:adj[v]){
					if(dp[u]>dp[v]+1){
						// if(u==n-1-3 and t==1) print(v,dp[v]);
						dp[u]=dp[v]+1;
						pq.push({dp[u],u});
					}
				}
			}
		}

		// if(t==1){
		// 	print(dp[n-1-3],d1[n-1-3]);
		// }

		rep(v,n){
			dp[v]=min(dp[v],d12[v]);
			if(!t){
				pns[v]=min(pns[v],dp[v]);
			}else{
				pns[n-1-v]=min(pns[n-1-v],dp[v]);
			}
		}

		rep(i,n){
			a[i].fi=n-1-a[i].fi;
			a[i].se=n-1-a[i].se;
			swap(a[i].fi,a[i].se);
		}
		reverse(all(a));
	}

	int q;
	cin>>q;
	rep(i,q){
		int x;
		cin>>x;
		x-=1;
		print(pns[x]==inf?-1:pns[x]);
	}
}

signed main(){
_3M8yqhy;
	slv();
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 1230 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1104 KB Output is correct
12 Correct 2 ms 1016 KB Output is correct
13 Correct 4 ms 1268 KB Output is correct
14 Correct 3 ms 1352 KB Output is correct
15 Correct 2 ms 1052 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1104 KB Output is correct
12 Correct 2 ms 1016 KB Output is correct
13 Correct 4 ms 1268 KB Output is correct
14 Correct 3 ms 1352 KB Output is correct
15 Correct 2 ms 1052 KB Output is correct
16 Correct 134 ms 37372 KB Output is correct
17 Correct 68 ms 32584 KB Output is correct
18 Correct 240 ms 51712 KB Output is correct
19 Correct 216 ms 50044 KB Output is correct
20 Correct 80 ms 32424 KB Output is correct
21 Correct 82 ms 34016 KB Output is correct
22 Correct 223 ms 54488 KB Output is correct
23 Correct 206 ms 47328 KB Output is correct
24 Correct 192 ms 42832 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1104 KB Output is correct
12 Correct 2 ms 1016 KB Output is correct
13 Correct 4 ms 1268 KB Output is correct
14 Correct 3 ms 1352 KB Output is correct
15 Correct 2 ms 1052 KB Output is correct
16 Correct 134 ms 37372 KB Output is correct
17 Correct 68 ms 32584 KB Output is correct
18 Correct 240 ms 51712 KB Output is correct
19 Correct 216 ms 50044 KB Output is correct
20 Correct 80 ms 32424 KB Output is correct
21 Correct 82 ms 34016 KB Output is correct
22 Correct 223 ms 54488 KB Output is correct
23 Correct 206 ms 47328 KB Output is correct
24 Correct 192 ms 42832 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 150 ms 40224 KB Output is correct
28 Correct 70 ms 33144 KB Output is correct
29 Correct 81 ms 32460 KB Output is correct
30 Correct 79 ms 34064 KB Output is correct
31 Correct 152 ms 40120 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 1230 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -