oj.uz

Submission #41413

# Submission time Handle Problem Language Result Execution time Memory
41413 2018-02-17T07:41:55 Z RockyB Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 42132 KB 
/// In The Name Of God
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
 
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define nl '\n'
#define ioi exit(0);
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)3e4 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
 
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
using namespace std;
 
int n, m;
int sta, fn;
int b[N], p[N];
vector < pair <int, int> > g[N];
vector <int> a[N], dv[N];

ll d[N];
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> p[i];
		a[b[i]].pb(p[i]);
		if (i == 1) sta = b[i];
		if (i == 2) fn = b[i];
	}
	for (int i = 0; i < n; i++) {
		if (sz(a[i])) sort(all(a[i]));
	}

	for (int i = 30000; i >= 1; i--) {
		for (int j = i; j <= 30000; j += i) {
			dv[j].pb(i);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			int df = abs(i - j);
			for (auto it : dv[df]) {
				if (binary_search(all(a[i]), it)) {
					g[i].pb({j, df / it});
					break;
				}
			}
		}
	}

	set < pair <ll, int > > st;
	memset(d, 0x3f, sizeof(d));
	st.insert({0, sta});
	d[sta] = 0;
	while (sz(st)) {
		pair <ll, int> v = *st.begin();
		st.erase(st.begin());
		for (auto to : g[v.s]) {
			if (d[to.f] > v.f + to.s) {
				st.erase({d[to.f], to.f});
				d[to.f] = v.f + to.s;
				st.insert({d[to.f], to.f});
			}
		}
	}
	if (d[fn] >= linf) cout << -1;
	else cout << d[fn];
	ioi
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4856 KB Output is correct
2 Correct 18 ms 4960 KB Output is correct
3 Correct 18 ms 5012 KB Output is correct
4 Correct 18 ms 5084 KB Output is correct
5 Correct 17 ms 5084 KB Output is correct
6 Correct 21 ms 5084 KB Output is correct
7 Correct 19 ms 5120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5156 KB Output is correct
2 Correct 18 ms 5156 KB Output is correct
3 Correct 20 ms 5156 KB Output is correct
4 Correct 19 ms 5156 KB Output is correct
5 Correct 20 ms 5156 KB Output is correct
6 Correct 23 ms 5156 KB Output is correct
7 Correct 19 ms 5156 KB Output is correct
8 Correct 19 ms 5156 KB Output is correct
9 Correct 21 ms 5156 KB Output is correct
10 Correct 21 ms 5156 KB Output is correct
11 Correct 21 ms 5292 KB Output is correct
12 Correct 20 ms 5292 KB Output is correct
13 Correct 21 ms 5292 KB Output is correct
14 Correct 18 ms 5292 KB Output is correct
15 Correct 21 ms 5292 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5292 KB Output is correct
2 Correct 18 ms 5292 KB Output is correct
3 Correct 19 ms 5292 KB Output is correct
4 Correct 19 ms 5292 KB Output is correct
5 Correct 17 ms 5292 KB Output is correct
6 Correct 18 ms 5292 KB Output is correct
7 Correct 17 ms 5292 KB Output is correct
8 Correct 17 ms 5292 KB Output is correct
9 Correct 20 ms 5292 KB Output is correct
10 Correct 21 ms 5292 KB Output is correct
11 Correct 24 ms 5356 KB Output is correct
12 Correct 19 ms 5356 KB Output is correct
13 Correct 20 ms 5356 KB Output is correct
14 Correct 20 ms 5356 KB Output is correct
15 Correct 19 ms 5356 KB Output is correct
16 Correct 25 ms 5356 KB Output is correct
17 Correct 71 ms 5356 KB Output is correct
18 Correct 267 ms 5356 KB Output is correct
19 Correct 339 ms 5356 KB Output is correct
20 Correct 427 ms 37532 KB Output is correct
21 Correct 34 ms 37532 KB Output is correct
22 Correct 276 ms 37532 KB Output is correct
23 Correct 249 ms 37532 KB Output is correct
24 Correct 335 ms 37532 KB Output is correct
25 Correct 416 ms 37532 KB Output is correct
26 Correct 335 ms 37532 KB Output is correct
27 Correct 339 ms 37532 KB Output is correct
28 Correct 401 ms 37532 KB Output is correct
29 Correct 323 ms 37532 KB Output is correct
30 Correct 334 ms 37532 KB Output is correct
31 Correct 324 ms 37532 KB Output is correct
32 Correct 323 ms 37532 KB Output is correct
33 Correct 325 ms 37532 KB Output is correct
34 Correct 328 ms 37532 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37532 KB Output is correct
2 Correct 19 ms 37532 KB Output is correct
3 Correct 20 ms 37532 KB Output is correct
4 Correct 20 ms 37532 KB Output is correct
5 Correct 28 ms 37532 KB Output is correct
6 Correct 18 ms 37532 KB Output is correct
7 Correct 18 ms 37532 KB Output is correct
8 Correct 18 ms 37532 KB Output is correct
9 Correct 20 ms 37532 KB Output is correct
10 Correct 21 ms 37532 KB Output is correct
11 Correct 29 ms 37532 KB Output is correct
12 Correct 19 ms 37532 KB Output is correct
13 Correct 23 ms 37532 KB Output is correct
14 Correct 20 ms 37532 KB Output is correct
15 Correct 21 ms 37532 KB Output is correct
16 Correct 26 ms 37532 KB Output is correct
17 Correct 77 ms 37532 KB Output is correct
18 Correct 298 ms 37532 KB Output is correct
19 Correct 343 ms 37532 KB Output is correct
20 Correct 421 ms 37532 KB Output is correct
21 Correct 34 ms 37532 KB Output is correct
22 Correct 284 ms 37532 KB Output is correct
23 Correct 248 ms 37532 KB Output is correct
24 Correct 341 ms 37532 KB Output is correct
25 Correct 379 ms 37532 KB Output is correct
26 Correct 330 ms 37532 KB Output is correct
27 Correct 328 ms 37532 KB Output is correct
28 Correct 391 ms 37532 KB Output is correct
29 Correct 348 ms 37532 KB Output is correct
30 Correct 332 ms 37532 KB Output is correct
31 Correct 314 ms 37532 KB Output is correct
32 Correct 330 ms 37532 KB Output is correct
33 Correct 328 ms 37532 KB Output is correct
34 Correct 322 ms 37532 KB Output is correct
35 Correct 294 ms 37532 KB Output is correct
36 Correct 136 ms 37532 KB Output is correct
37 Correct 498 ms 37532 KB Output is correct
38 Correct 545 ms 37532 KB Output is correct
39 Correct 554 ms 37532 KB Output is correct
40 Correct 520 ms 37532 KB Output is correct
41 Correct 520 ms 37532 KB Output is correct
42 Correct 327 ms 37532 KB Output is correct
43 Correct 310 ms 37532 KB Output is correct
44 Correct 399 ms 39956 KB Output is correct
45 Correct 340 ms 39956 KB Output is correct
46 Correct 350 ms 39956 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39956 KB Output is correct
2 Correct 25 ms 39956 KB Output is correct
3 Correct 24 ms 39956 KB Output is correct
4 Correct 19 ms 39956 KB Output is correct
5 Correct 19 ms 39956 KB Output is correct
6 Correct 17 ms 39956 KB Output is correct
7 Correct 18 ms 39956 KB Output is correct
8 Correct 19 ms 39956 KB Output is correct
9 Correct 18 ms 39956 KB Output is correct
10 Correct 26 ms 39956 KB Output is correct
11 Correct 20 ms 39956 KB Output is correct
12 Correct 27 ms 39956 KB Output is correct
13 Correct 19 ms 39956 KB Output is correct
14 Correct 21 ms 39956 KB Output is correct
15 Correct 18 ms 39956 KB Output is correct
16 Correct 26 ms 39956 KB Output is correct
17 Correct 72 ms 39956 KB Output is correct
18 Correct 289 ms 39956 KB Output is correct
19 Correct 340 ms 39956 KB Output is correct
20 Correct 441 ms 40000 KB Output is correct
21 Correct 29 ms 40000 KB Output is correct
22 Correct 274 ms 40000 KB Output is correct
23 Correct 233 ms 40000 KB Output is correct
24 Correct 340 ms 40000 KB Output is correct
25 Correct 354 ms 40000 KB Output is correct
26 Correct 307 ms 40000 KB Output is correct
27 Correct 341 ms 40000 KB Output is correct
28 Correct 376 ms 40000 KB Output is correct
29 Correct 315 ms 40000 KB Output is correct
30 Correct 305 ms 40000 KB Output is correct
31 Correct 313 ms 40000 KB Output is correct
32 Correct 310 ms 40000 KB Output is correct
33 Correct 313 ms 40000 KB Output is correct
34 Correct 318 ms 40000 KB Output is correct
35 Correct 279 ms 40000 KB Output is correct
36 Correct 131 ms 40000 KB Output is correct
37 Correct 472 ms 40000 KB Output is correct
38 Correct 521 ms 40000 KB Output is correct
39 Correct 546 ms 40000 KB Output is correct
40 Correct 561 ms 40000 KB Output is correct
41 Correct 526 ms 40000 KB Output is correct
42 Correct 317 ms 40000 KB Output is correct
43 Correct 311 ms 40000 KB Output is correct
44 Correct 405 ms 42132 KB Output is correct
45 Correct 333 ms 42132 KB Output is correct
46 Correct 338 ms 42132 KB Output is correct
47 Execution timed out 1065 ms 42132 KB Time limit exceeded
48 Halted 0 ms 0 KB -