oj.uz

Submission #888924

# Submission time Handle Problem Language Result Execution time Memory
888924 2023-12-18T11:55:28 Z vjudge1 Passport (JOI23_passport) C++17
22 / 100
 2000 ms 57216 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(l[i]<x&&r[i]>y&&dist[l[i]][r[i]]>dist[x][y]+1){
					dist[l[i]][r[i]] = dist[x][y] + 1;
					q.push({dist[l[i]][r[i]],{l[i],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:86:6: warning: unused variable 'cnt' [-Wunused-variable]
   86 |  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:123:6: warning: unused variable 'cnt' [-Wunused-variable]
  123 |  int cnt=0;
      |      ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49496 KB Output is correct
2 Correct 24 ms 49492 KB Output is correct
3 Correct 23 ms 49496 KB Output is correct
4 Correct 57 ms 56332 KB Output is correct
5 Correct 50 ms 55628 KB Output is correct
6 Correct 50 ms 56012 KB Output is correct
7 Correct 47 ms 57216 KB Output is correct
8 Correct 43 ms 56012 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49500 KB Output is correct
2 Correct 23 ms 49500 KB Output is correct
3 Correct 24 ms 49500 KB Output is correct
4 Correct 24 ms 49444 KB Output is correct
5 Correct 23 ms 49500 KB Output is correct
6 Correct 23 ms 49572 KB Output is correct
7 Correct 24 ms 49500 KB Output is correct
8 Correct 24 ms 49496 KB Output is correct
9 Correct 24 ms 49492 KB Output is correct
10 Correct 26 ms 49640 KB Output is correct
11 Correct 65 ms 49500 KB Output is correct
12 Correct 58 ms 49496 KB Output is correct
13 Correct 64 ms 49632 KB Output is correct
14 Correct 55 ms 49496 KB Output is correct
15 Correct 62 ms 49500 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49500 KB Output is correct
2 Correct 23 ms 49500 KB Output is correct
3 Correct 24 ms 49500 KB Output is correct
4 Correct 24 ms 49444 KB Output is correct
5 Correct 23 ms 49500 KB Output is correct
6 Correct 23 ms 49572 KB Output is correct
7 Correct 24 ms 49500 KB Output is correct
8 Correct 24 ms 49496 KB Output is correct
9 Correct 24 ms 49492 KB Output is correct
10 Correct 26 ms 49640 KB Output is correct
11 Correct 65 ms 49500 KB Output is correct
12 Correct 58 ms 49496 KB Output is correct
13 Correct 64 ms 49632 KB Output is correct
14 Correct 55 ms 49496 KB Output is correct
15 Correct 62 ms 49500 KB Output is correct
16 Execution timed out 2076 ms 49984 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49500 KB Output is correct
2 Correct 23 ms 49500 KB Output is correct
3 Correct 24 ms 49500 KB Output is correct
4 Correct 24 ms 49444 KB Output is correct
5 Correct 23 ms 49500 KB Output is correct
6 Correct 23 ms 49572 KB Output is correct
7 Correct 24 ms 49500 KB Output is correct
8 Correct 24 ms 49496 KB Output is correct
9 Correct 24 ms 49492 KB Output is correct
10 Correct 26 ms 49640 KB Output is correct
11 Correct 65 ms 49500 KB Output is correct
12 Correct 58 ms 49496 KB Output is correct
13 Correct 64 ms 49632 KB Output is correct
14 Correct 55 ms 49496 KB Output is correct
15 Correct 62 ms 49500 KB Output is correct
16 Execution timed out 2076 ms 49984 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49496 KB Output is correct
2 Correct 24 ms 49492 KB Output is correct
3 Correct 23 ms 49496 KB Output is correct
4 Correct 57 ms 56332 KB Output is correct
5 Correct 50 ms 55628 KB Output is correct
6 Correct 50 ms 56012 KB Output is correct
7 Correct 47 ms 57216 KB Output is correct
8 Correct 43 ms 56012 KB Output is correct
9 Correct 23 ms 49500 KB Output is correct
10 Correct 23 ms 49500 KB Output is correct
11 Correct 24 ms 49500 KB Output is correct
12 Correct 24 ms 49444 KB Output is correct
13 Correct 23 ms 49500 KB Output is correct
14 Correct 23 ms 49572 KB Output is correct
15 Correct 24 ms 49500 KB Output is correct
16 Correct 24 ms 49496 KB Output is correct
17 Correct 24 ms 49492 KB Output is correct
18 Correct 26 ms 49640 KB Output is correct
19 Correct 65 ms 49500 KB Output is correct
20 Correct 58 ms 49496 KB Output is correct
21 Correct 64 ms 49632 KB Output is correct
22 Correct 55 ms 49496 KB Output is correct
23 Correct 62 ms 49500 KB Output is correct
24 Execution timed out 2076 ms 49984 KB Time limit exceeded
25 Halted 0 ms 0 KB -