Submission #745030

#	Time	Username	Problem	Language	Result	Execution time	Memory
745030		red24	Passport (JOI23_passport)	C++14	0 / 100	2081 ms	1048576 KiB

passport

#include "bits/stdc++.h"
using namespace std;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define mp make_pair
#define ll long long
#define pb push_back
#define vpi vector<pi>
#define all(x) x.begin()+1,x.end()
const int INF = (int)1e17;

// figure out most of the implementation details before you
// implement the whole thing

// try to change the order in which you imlpement certain
// processes (doesnt have to be in chronological order) to
// simplify the implementation

// try to think in different directions and if one direction
// is giving too many edge cases its probably not the intended way

// try to have a fairly clear idea of each segment of code you
// are going to write and divide your idea into organized
// subideas instead of just trying to go off a vague idea without
// figuring out any implementation details

// dont spend too much time on a problem get the subtasks and gtfo
// if you already spent too much time on it 

// try to implement subtasks if full implementation is big 
// or youre out of ideas to optimize

int n;
vvi dp;
vi L, R;

void dfs(int l, int r, int c)
{
	//cout << ' ' << l << ' ' << r << ' ' << c << '\n';
	if (dp[l][r] < c) return;
	dp[l][r] = c;
	rep(i, l, r) 
	{
		pi curr = mp(l, r);
		pi next = mp(min(l, L[i]), max(r, R[i]));
		if (curr != next) dfs(next.first, next.second, c+1);
	}
}

void solve()
{
	cin >> n;
	L = vi(n+1); R = vi(n+1);
	rep(i, 1, n) cin >> L[i] >> R[i];
	dp = vvi(n+1, vi(n+1, INF));

	int w; cin >> w;
	int s; cin >> s;

	dp[s][s] = 0;
	dfs(s, s, 0);
	cout << (dp[1][n] == INF ? -1 : dp[1][n]);
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	auto begin = std::chrono::high_resolution_clock::now();
	int t = 1; 
	//cin >> t;
	rep(i, 1, t)
	{
		//cout << "Case " << i << ":\n";
		solve();
	}

	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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