Submission #888823

#	Time	Username	Problem	Language	Result	Execution time	Memory
888823		vjudge1	Passport (JOI23_passport)	C++17	16 / 100	2019 ms	1048576 KiB

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 (stderr)

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

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46