Submission #888823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888823	2023-12-18T08:12:09 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;
				}
				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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Runtime error	573 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 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	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	21 ms	1880 KB	Output is correct
12	Correct	56 ms	2276 KB	Output is correct
13	Correct	73 ms	2140 KB	Output is correct
14	Correct	62 ms	1884 KB	Output is correct
15	Correct	286 ms	3368 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 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	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	21 ms	1880 KB	Output is correct
12	Correct	56 ms	2276 KB	Output is correct
13	Correct	73 ms	2140 KB	Output is correct
14	Correct	62 ms	1884 KB	Output is correct
15	Correct	286 ms	3368 KB	Output is correct
16	Execution timed out	2019 ms	112208 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 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	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	21 ms	1880 KB	Output is correct
12	Correct	56 ms	2276 KB	Output is correct
13	Correct	73 ms	2140 KB	Output is correct
14	Correct	62 ms	1884 KB	Output is correct
15	Correct	286 ms	3368 KB	Output is correct
16	Execution timed out	2019 ms	112208 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Runtime error	573 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-