oj.uz

Submission #888914

# Submission time Handle Problem Language Result Execution time Memory
888914 2023-12-18T11:43:39 Z vjudge1 Passport (JOI23_passport) C++17
6 / 100
 60 ms 59016 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define pb push_back
#define int long long
#define f first
#define s second
#define pii pair<int,int>
const int mod= 1e9 +7;
const int N=2505;

vector<vector<int>> dist(N, vector<int> (N, mod));

void solve(){
	int n,m,k;

	cin>>n;
	
	if(n<=2505){
		vector<int>l(n+1),r(n+1);
	
		for(int i = 0;i<n;i++){
			int a,b;
			cin>>l[i]>>r[i];
			l[i]--;r[i]--;
		}
	
		int h,x;
		cin>>h>>x;
		x--;
		priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>> > q;
		
		q.push({1,{l[x],r[x]}});
		dist[l[x]][r[x]] = 1;
		
		int ml = -1,mr = -1;
		
		while(!q.empty()){
			auto [w,t] = q.top();
			int x = t.f,y = t.s;
			q.pop();
			if(dist[x][y]<w)continue;
			int ml = x;int mr = y;
			for(int i = x;i<=y;i++){
				ml = min(ml,l[i]);
				mr = max(mr,r[i]);
			}
			if(x<y){
				if(dist[ml][y]>dist[x][y] + 1){
					dist[ml][y] = dist[x][y] + 1;
					q.push({dist[ml][y],{ml,y}});
				}
				if(dist[x][mr]>dist[x][y] + 1){
					dist[x][mr] = dist[x][y] + 1;
					q.push({dist[x][mr],{x,mr}});
				}
				if(dist[x+1][y-1]>dist[x][y]){
					dist[x+1][y-1] = dist[x][y];
					q.push({dist[x+1][y-1],{x+1,y-1}});
				}
//				dist[x][mr] = dist[x][y] + 1;
			}
			else if(x==y){
				if(dist[l[x]][r[x]]>dist[x][y] + 1){
					dist[l[x]][r[x]] = dist[x][y] + 1;
					q.push({dist[l[x]][r[x]],{l[x],r[x]}});
				}
			}
			
		}
	
		if(dist[0][n-1]==mod)cout<<-1<<"\n";
		else cout<<dist[0][n-1]<<"\n";
	
		
	}
	else{
		vector<pii>v;vector<int>pref(n+1,0);
	int r1 = 1;
	int cnt = 1;
	for(int i = 0;i<n;i++){
		int l,r;
		cin>>l>>r;
		v.pb({l,r});
		if(i==0)r1 = r;
		if(i==n)cout<<"Baiysh want a rulet!!!!!!!!!!!!!!!!!!!!!!\n";
		else{
			pref[i+1] = max(pref[i],r);
		}
	}
	int last = -1;int ans = 1;
	while(r1!=n){
		last = r1;
		r1 = pref[r1];
		ans++;
		if(last==r1){
			cout<<-1<<"\n";
			exit(0);
		}
	}
	cout<<ans<<"\n";
	}
	






}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int cnt=0;
	int tt=1;
	while(tt--)solve();

}

Compilation message

passport.cpp: In function 'void solve()':
passport.cpp:24:8: warning: unused variable 'a' [-Wunused-variable]
   24 |    int a,b;
      |        ^
passport.cpp:24:10: warning: unused variable 'b' [-Wunused-variable]
   24 |    int a,b;
      |          ^
passport.cpp:37:7: warning: unused variable 'ml' [-Wunused-variable]
   37 |   int ml = -1,mr = -1;
      |       ^~
passport.cpp:37:15: warning: unused variable 'mr' [-Wunused-variable]
   37 |   int ml = -1,mr = -1;
      |               ^~
passport.cpp:81:6: warning: unused variable 'cnt' [-Wunused-variable]
   81 |  int cnt = 1;
      |      ^~~
passport.cpp:16:8: warning: unused variable 'm' [-Wunused-variable]
   16 |  int n,m,k;
      |        ^
passport.cpp:16:10: warning: unused variable 'k' [-Wunused-variable]
   16 |  int n,m,k;
      |          ^
passport.cpp: In function 'int main()':
passport.cpp:118:6: warning: unused variable 'cnt' [-Wunused-variable]
  118 |  int cnt=0;
      |      ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49496 KB Output is correct
2 Correct 23 ms 49464 KB Output is correct
3 Correct 24 ms 49488 KB Output is correct
4 Correct 50 ms 56260 KB Output is correct
5 Correct 50 ms 57028 KB Output is correct
6 Correct 60 ms 59016 KB Output is correct
7 Correct 47 ms 58308 KB Output is correct
8 Correct 43 ms 57412 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49500 KB Output is correct
2 Correct 23 ms 49620 KB Output is correct
3 Correct 22 ms 49500 KB Output is correct
4 Correct 23 ms 49416 KB Output is correct
5 Correct 24 ms 49492 KB Output is correct
6 Correct 25 ms 49500 KB Output is correct
7 Correct 23 ms 49500 KB Output is correct
8 Incorrect 23 ms 49500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49500 KB Output is correct
2 Correct 23 ms 49620 KB Output is correct
3 Correct 22 ms 49500 KB Output is correct
4 Correct 23 ms 49416 KB Output is correct
5 Correct 24 ms 49492 KB Output is correct
6 Correct 25 ms 49500 KB Output is correct
7 Correct 23 ms 49500 KB Output is correct
8 Incorrect 23 ms 49500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49500 KB Output is correct
2 Correct 23 ms 49620 KB Output is correct
3 Correct 22 ms 49500 KB Output is correct
4 Correct 23 ms 49416 KB Output is correct
5 Correct 24 ms 49492 KB Output is correct
6 Correct 25 ms 49500 KB Output is correct
7 Correct 23 ms 49500 KB Output is correct
8 Incorrect 23 ms 49500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49496 KB Output is correct
2 Correct 23 ms 49464 KB Output is correct
3 Correct 24 ms 49488 KB Output is correct
4 Correct 50 ms 56260 KB Output is correct
5 Correct 50 ms 57028 KB Output is correct
6 Correct 60 ms 59016 KB Output is correct
7 Correct 47 ms 58308 KB Output is correct
8 Correct 43 ms 57412 KB Output is correct
9 Correct 24 ms 49500 KB Output is correct
10 Correct 23 ms 49620 KB Output is correct
11 Correct 22 ms 49500 KB Output is correct
12 Correct 23 ms 49416 KB Output is correct
13 Correct 24 ms 49492 KB Output is correct
14 Correct 25 ms 49500 KB Output is correct
15 Correct 23 ms 49500 KB Output is correct
16 Incorrect 23 ms 49500 KB Output isn't correct
17 Halted 0 ms 0 KB -