답안 #41413 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41413	2018-02-17T07:41:55 Z	RockyB	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	42132 KB

skyscraper

/// 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #41413

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0