답안 #888761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888761	2023-12-18T07:24:23 Z	vjudge1	Passport (JOI23_passport)	C++17	22 / 100	2000 ms	205140 KB

passport

/*

author : abushbandit
contest : ---

*/

#include "bits/stdc++.h"

using namespace std;

#define int long long

void solve(int tc){
	
	int n;
	cin >> n;
	vector<pair<int,int>> a(n + 1);
	for(int i = 1;i <= n;i++){
		int l,r;
		cin >> l >> r;
		a[i] = {l,r};
	}
	
 	
    int q;
	cin >> q;
	for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        if(x == 1){
        	
        	int i = 1,lst = a[1].second,cnt = 0;
        	bool check = 0;
        	while(true){
        		cnt++;
        		int mx = 0;
        		while(i <= n && i <= lst){
        			mx = max(mx,a[i].second);
        			i++;
				}
				if(i > n){
					break;
				} else if(lst < mx){
					lst = mx;
				} else{
					check = 1;
					break;
				}
			}
        	
        	if(check){
        		cout << -1 << "\n";
			} else{
				cout << cnt << "\n";
			}
        	
        	break;
        	
		} else{
			vector<vector<int>> dis(n + 1, vector<int> (n + 1,1e18));
	        vector<vector<int>> vis(n + 1, vector<int> (n + 1,0));
	 
	        set<vector<int>> st;
	        dis[a[x].first][a[x].second] = 1;
	       	st.insert({1,a[x].first,a[x].second});
	        while(!st.empty()){
	            int l = (*st.begin())[1], r = (*st.begin())[2];
	            st.erase(st.begin());
	            if(vis[l][r])continue;
	            vis[l][r] = 1;
	            for(int i = l;i <= r;i++){
	                for(int j = r;j <= max(r,a[i].second);j++){
	                    for(int k = l;k >= min(l,a[i].first);k--){
	                        if(dis[l][r] + 1 < dis[k][j]){
	                            st.insert({dis[l][r] + 1,k,j});
	                            dis[k][j] = dis[l][r] + 1;
	                        }
	                    }
	                }
	            }
	        }
	        if(dis[1][n] == 1e18){
	        	cout << "-1\n";
			} else{
				cout << dis[1][n] << "\n";
			}
		}
	        
    }
	
}

signed main(){

//	start_file("");

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	int test_cases = 1;
//	cin >> test_cases ;
	for(int tc = 1;tc <= test_cases;++ tc){
		solve(tc);
	}	

}

/*



*/

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	24 ms	3420 KB	Output is correct
5	Correct	29 ms	3416 KB	Output is correct
6	Correct	23 ms	3420 KB	Output is correct
7	Correct	19 ms	3420 KB	Output is correct
8	Correct	17 ms	2908 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	248 ms	2568 KB	Output is correct
12	Correct	16 ms	1880 KB	Output is correct
13	Correct	103 ms	1880 KB	Output is correct
14	Correct	30 ms	2140 KB	Output is correct
15	Correct	6 ms	1884 KB	Output is correct

Subtask #3

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	248 ms	2568 KB	Output is correct
12	Correct	16 ms	1880 KB	Output is correct
13	Correct	103 ms	1880 KB	Output is correct
14	Correct	30 ms	2140 KB	Output is correct
15	Correct	6 ms	1884 KB	Output is correct
16	Execution timed out	2076 ms	205140 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	248 ms	2568 KB	Output is correct
12	Correct	16 ms	1880 KB	Output is correct
13	Correct	103 ms	1880 KB	Output is correct
14	Correct	30 ms	2140 KB	Output is correct
15	Correct	6 ms	1884 KB	Output is correct
16	Execution timed out	2076 ms	205140 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	24 ms	3420 KB	Output is correct
5	Correct	29 ms	3416 KB	Output is correct
6	Correct	23 ms	3420 KB	Output is correct
7	Correct	19 ms	3420 KB	Output is correct
8	Correct	17 ms	2908 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	248 ms	2568 KB	Output is correct
20	Correct	16 ms	1880 KB	Output is correct
21	Correct	103 ms	1880 KB	Output is correct
22	Correct	30 ms	2140 KB	Output is correct
23	Correct	6 ms	1884 KB	Output is correct
24	Execution timed out	2076 ms	205140 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-