제출 #888871

#제출 시각아이디문제언어결과실행 시간메모리
888871vjudge1Passport (JOI23_passport)C++17
22 / 100
2072 ms57024 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=2505;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}

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;
		
		while(!q.empty()){
			auto [w,t] = q.top();
			int x = t.f,y = t.s;
			q.pop();
			if(dist[x][y]<w)continue;
			
			for(int i = x;i<=y;i++){
				int mxl = min(x,l[i]),mxr = max(r[i],y);
				if(umin(dist[mxl][mxr],dist[x][y] + 1)){
					q.push({dist[mxl][mxr],{mxl,mxr}});
				}
			}
			
		}
	
		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();

}


컴파일 시 표준 에러 (stderr) 메시지

passport.cpp: In function 'void solve()':
passport.cpp:45:8: warning: unused variable 'a' [-Wunused-variable]
   45 |    int a,b;
      |        ^
passport.cpp:45:10: warning: unused variable 'b' [-Wunused-variable]
   45 |    int a,b;
      |          ^
passport.cpp:81:6: warning: unused variable 'cnt' [-Wunused-variable]
   81 |  int cnt = 1;
      |      ^~~
passport.cpp:37:8: warning: unused variable 'm' [-Wunused-variable]
   37 |  int n,m,k;
      |        ^
passport.cpp:37:10: warning: unused variable 'k' [-Wunused-variable]
   37 |  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...