답안 #888831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888831	2023-12-18T08:17:42 Z	vjudge1	Passport (JOI23_passport)	C++17	16 / 100	2000 ms	1048576 KB

passport

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;
using namespace __gnu_pbds;

const int mod = 998244353;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1e5 + 5;

void solve(){
	int n;
	cin >> n;
	vector<pair<int,int> > a(n);
	for(auto &[i,j] : a) cin >> i >> j;
	int q;
	cin >> q;
	while(q--){
		int x; cin >> x;
		set<pair<int,int> > q;
		q.insert({a[x-1].ff,a[x-1].ss});
		int dis[n+1][n+1];
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				dis[i][j] = 1e18;
			}
		}
		dis[a[x-1].ff][a[x-1].ss] = 1;
		while(!q.empty()){
			auto [l,r] = *q.begin();
			q.erase(q.begin());
			for(int t = l; t <= r; t++){
				auto [i,j] = a[t-1];
				if(i <= l && r <= j && dis[l][r] + 1 < dis[i][j]){
					q.erase({i,j});
					q.insert({i,j});
					dis[i][j] = dis[l][r] + 1;
					continue;
				}else if(i <= l && r <= j) continue;
				if(i <= r && dis[l][r] + 1 < dis[l][j]){
					q.erase({l,j});
					q.insert({l,j});
					dis[l][j] = dis[l][r] + 1;
				}
				if(l <= j && dis[l][r] + 1 < dis[i][r]){
					q.erase({i,r});
					q.insert({i,r});
					dis[i][r] = dis[l][r] + 1;
				}
			}
		}
		if(dis[1][n] == 1e18) cout << "-1\n";
		else cout << dis[1][n] << '\n';
	}
}

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

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

passport.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~

Subtask #1

0 / 6.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	Runtime error	540 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	496 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 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	20 ms	2112 KB	Output is correct
12	Correct	70 ms	2140 KB	Output is correct
13	Correct	70 ms	2176 KB	Output is correct
14	Correct	53 ms	2008 KB	Output is correct
15	Correct	289 ms	3160 KB	Output is correct

Subtask #3

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	496 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 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	20 ms	2112 KB	Output is correct
12	Correct	70 ms	2140 KB	Output is correct
13	Correct	70 ms	2176 KB	Output is correct
14	Correct	53 ms	2008 KB	Output is correct
15	Correct	289 ms	3160 KB	Output is correct
16	Execution timed out	2041 ms	112320 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	496 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 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	20 ms	2112 KB	Output is correct
12	Correct	70 ms	2140 KB	Output is correct
13	Correct	70 ms	2176 KB	Output is correct
14	Correct	53 ms	2008 KB	Output is correct
15	Correct	289 ms	3160 KB	Output is correct
16	Execution timed out	2041 ms	112320 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 46.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	Runtime error	540 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-