Submission #888914

#TimeUsernameProblemLanguageResultExecution timeMemory
888914vjudge1Passport (JOI23_passport)C++17
6 / 100
60 ms59016 KiB
#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 (stderr)

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;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...