oj.uz

Submission #513746

# Submission time Handle Problem Language Result Execution time Memory
513746 2022-01-17T13:41:54 Z BlackWhite Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1000 ms 199084 KB 
// author: BlackWhite
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define debugg(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
	for ( \
		auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
		blockTime.second; \
		debugg("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
	)

#define int long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll oo = 1e18;
const ld eps = 1e-9;
const string yes = "YES";
const string no = "NO";
const ld PI = acos(-1.0);
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> iv;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <ii> vp;
#define all(x) begin(x), end(x)
#define sz(x) ((int) x.size())
#define clrscr system("cls");
#define ENDL printf("\n");
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ins insert
#define pob pop_back
#define pof pop_front
#define el '\n'

#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define NAME "test"
inline void io(int x){
	if (!x){
		freopen(NAME".inp", "r", stdin);
		return;
	}
	if (x == 1){
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
		return;
	}
	freopen(NAME".out", "w", stdout);
}

int n, m;
const int N = 3e4 + 5;
ii sv[N];
vi p[N];
vector <vector <int>> dist(N);

void dijkstra(int s, int t, int minn, int maxx){
	for (int i = 1; i <= n; i++){
		dist[i].resize(n + 5, oo);
	}

	priority_queue <iii, vector <iii>, greater <iii>> pq;

	for (int x : p[s]){
		dist[s][x] = 0;
		pq.push(iii(0, ii(s, x)));
	}

	while(sz(pq)){
		int du = pq.top().fi;
		int u = pq.top().se.fi;
		int pw = pq.top().se.se;

		pq.pop();

		// debug(du, u, pw);

		if (u == t){
			cout << du << el;

			return;
		}

		if (u - pw >= 1 && dist[u - pw][pw] > du){
			dist[u - pw][pw] = du + 1;

			pq.push(iii(dist[u - pw][pw], ii(u - pw, pw)));
		}

		if (u + pw <= n && dist[u + pw][pw] > du){
			dist[u + pw][pw] = du + 1;

			pq.push(iii(dist[u + pw][pw], ii(u + pw, pw)));
		}

		for (int new_pw : p[u]){
			if (u - new_pw >= 1 && dist[u - new_pw][new_pw] > du){
				dist[u - new_pw][new_pw] = du + 1;

				pq.push(iii(dist[u - new_pw][new_pw], ii(u - new_pw, new_pw)));
			}

			if (u + new_pw <= n && dist[u + new_pw][new_pw] > du){
				dist[u + new_pw][new_pw] = du + 1;

				pq.push(iii(dist[u + new_pw][new_pw], ii(u + new_pw, new_pw)));
			}
		}
	}

	int res = oo;

	for (int i = minn; i <= maxx; i++){
		res = min(res, dist[t][i]);
	}

	cout << (res == oo ? -1 : res) << el;
}

inline void solve(){
	cin >> n >> m;
	int minn = oo, maxx = -1;
	for (int i = 1; i <= m; i++){
		cin >> sv[i].fi >> sv[i].se;

		sv[i].fi++;

		p[sv[i].fi].pb(sv[i].se);

		minn = min(minn, sv[i].se);
		maxx = max(maxx, sv[i].se);
	}

	dijkstra(sv[1].fi, sv[2].fi, minn, maxx);
}

signed main()
{
	Fast
	// io(1);

	int test_case = 1;
	// cin >> test_case;
	for (int tt = 1; tt <= test_case; tt++){
		// cout << "Case #" << tt << ": ";

		solve();
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 1 ms 1740 KB Output is correct
5 Correct 1 ms 1792 KB Output is correct
6 Correct 1 ms 1740 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 1 ms 1740 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 1 ms 1740 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1744 KB Output is correct
13 Execution timed out 1076 ms 199056 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1740 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 1 ms 1740 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Execution timed out 1039 ms 198932 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 1 ms 1736 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Execution timed out 1095 ms 199084 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1740 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 1 ms 1732 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1868 KB Output is correct
13 Execution timed out 1096 ms 198924 KB Time limit exceeded
14 Halted 0 ms 0 KB -