oj.uz

Submission #583182

# Submission time Handle Problem Language Result Execution time Memory
583182 2022-06-25T02:54:18 Z Justin1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 201 ms 201108 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct edge{
	int v, c;
};
 
const int maxpow = 1;
const int dqsize = 5500000;
 
int n,m,k,x,y,z;
int pos[3], power[3];
vector<edge> gph[5500000];
int dis[5500000];
vector<bool> inq(5500000);
int nxt[5500000], head, tail;
 
int f(int i, int j) { //2d to 1d
	return (i-1)*maxpow+j;
}
 
bool empty() {
	return head == tail;
}
 
void push_back(int x) {
	nxt[tail] = x;
	tail = (tail+1) % dqsize;
}
 
void push_front(int x) {
	head = (head-1+dqsize) % dqsize;
	nxt[head] = x;
}
 
int front() {
	return nxt[head];
}
 
int back() {
	return nxt[(tail-1+dqsize) % dqsize];
}
 
void pop_front() {
	head = (head+1) % dqsize;
}
 
void pop_back() {
	tail = (tail-1+dqsize) % dqsize;
}
 
void spfa() {
	for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9;
	dis[n*maxpow+pos[1]] = 0;
	push_back(n*maxpow+pos[1]);
	inq[n*maxpow+pos[1]] = 1;
	while (!empty()) {
		auto tmp = front();
		pop_front();
		inq[tmp] = 0;
		for (auto i : gph[tmp]) {
			if (dis[tmp] + i.c < dis[i.v]) {
				dis[i.v] = dis[tmp] + i.c;
				if (!inq[i.v]) push_back(i.v);
				inq[i.v] = 1;
				if (dis[back()] < dis[front()]){
					push_front(back());
					pop_back();
				}
			}
		}
	}
	if (dis[n*maxpow+pos[2]] == 1e9) cout << "-1\n";
	else cout << dis[n*maxpow+pos[2]] << '\n';
}
 
int main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		x++;
		if (y > maxpow) {
			for (int j = x - y, c = 1; j >= 1; j -= y, c++) 
				gph[n*maxpow+x].push_back({n*maxpow+j,c});
			for (int j = x + y, c = 1; j <= n; j += y, c++) 
				gph[n*maxpow+x].push_back({n*maxpow+j,c});
		} else {
			gph[n*maxpow+x].push_back({f(x,y),0});
		}
		if (i <= 2) pos[i] = x, power[i] = y;
	}
	for (int i = 1; i <= maxpow; i++) { //pow
		for (int j = 1; j <= i; j++) {
			for (int l = j; l+i <= n; l += i) { //pos
				gph[f(l,i)].push_back({f(l+i,i),1});
				gph[f(l+i,i)].push_back({f(l,i),1});
			}
		}
		for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*maxpow+j,0});
	}
	spfa();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 130156 KB Output is correct
2 Correct 69 ms 130064 KB Output is correct
3 Correct 73 ms 130068 KB Output is correct
4 Correct 64 ms 130124 KB Output is correct
5 Correct 74 ms 130036 KB Output is correct
6 Correct 66 ms 130064 KB Output is correct
7 Correct 63 ms 130156 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130028 KB Output is correct
2 Correct 65 ms 130084 KB Output is correct
3 Correct 70 ms 130144 KB Output is correct
4 Correct 61 ms 130132 KB Output is correct
5 Correct 64 ms 130040 KB Output is correct
6 Correct 68 ms 130100 KB Output is correct
7 Correct 69 ms 130080 KB Output is correct
8 Correct 63 ms 130156 KB Output is correct
9 Correct 64 ms 130072 KB Output is correct
10 Correct 66 ms 130052 KB Output is correct
11 Correct 63 ms 130180 KB Output is correct
12 Correct 61 ms 130076 KB Output is correct
13 Correct 66 ms 130148 KB Output is correct
14 Correct 70 ms 130216 KB Output is correct
15 Correct 72 ms 130200 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 130140 KB Output is correct
2 Correct 67 ms 130148 KB Output is correct
3 Correct 64 ms 130100 KB Output is correct
4 Correct 63 ms 130036 KB Output is correct
5 Correct 65 ms 130176 KB Output is correct
6 Correct 67 ms 130152 KB Output is correct
7 Correct 68 ms 130160 KB Output is correct
8 Correct 68 ms 130100 KB Output is correct
9 Correct 72 ms 130124 KB Output is correct
10 Correct 63 ms 130068 KB Output is correct
11 Correct 60 ms 130220 KB Output is correct
12 Correct 63 ms 130128 KB Output is correct
13 Correct 68 ms 130152 KB Output is correct
14 Correct 66 ms 130176 KB Output is correct
15 Correct 63 ms 130172 KB Output is correct
16 Correct 66 ms 130180 KB Output is correct
17 Correct 73 ms 130316 KB Output is correct
18 Correct 66 ms 130296 KB Output is correct
19 Correct 76 ms 130336 KB Output is correct
20 Correct 66 ms 130380 KB Output is correct
21 Correct 65 ms 130088 KB Output is correct
22 Correct 61 ms 130344 KB Output is correct
23 Correct 65 ms 130344 KB Output is correct
24 Correct 68 ms 130324 KB Output is correct
25 Correct 65 ms 130288 KB Output is correct
26 Correct 65 ms 130396 KB Output is correct
27 Correct 61 ms 130292 KB Output is correct
28 Correct 64 ms 130512 KB Output is correct
29 Correct 66 ms 130840 KB Output is correct
30 Correct 67 ms 130456 KB Output is correct
31 Correct 68 ms 130540 KB Output is correct
32 Correct 62 ms 130500 KB Output is correct
33 Correct 63 ms 131388 KB Output is correct
34 Correct 63 ms 131396 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 130124 KB Output is correct
2 Correct 77 ms 130092 KB Output is correct
3 Correct 67 ms 130068 KB Output is correct
4 Correct 64 ms 130100 KB Output is correct
5 Correct 65 ms 130148 KB Output is correct
6 Correct 59 ms 130104 KB Output is correct
7 Correct 66 ms 130124 KB Output is correct
8 Correct 64 ms 130104 KB Output is correct
9 Correct 65 ms 130108 KB Output is correct
10 Correct 69 ms 130136 KB Output is correct
11 Correct 64 ms 130132 KB Output is correct
12 Correct 62 ms 130160 KB Output is correct
13 Correct 64 ms 130152 KB Output is correct
14 Correct 68 ms 130192 KB Output is correct
15 Correct 74 ms 130124 KB Output is correct
16 Correct 60 ms 130148 KB Output is correct
17 Correct 68 ms 130380 KB Output is correct
18 Correct 63 ms 130308 KB Output is correct
19 Correct 63 ms 130340 KB Output is correct
20 Correct 73 ms 130336 KB Output is correct
21 Correct 72 ms 130168 KB Output is correct
22 Correct 64 ms 130328 KB Output is correct
23 Correct 62 ms 130336 KB Output is correct
24 Correct 71 ms 130360 KB Output is correct
25 Correct 76 ms 130360 KB Output is correct
26 Correct 66 ms 130304 KB Output is correct
27 Correct 65 ms 130380 KB Output is correct
28 Correct 62 ms 130492 KB Output is correct
29 Correct 64 ms 130884 KB Output is correct
30 Correct 77 ms 130516 KB Output is correct
31 Correct 64 ms 130548 KB Output is correct
32 Correct 63 ms 130484 KB Output is correct
33 Correct 66 ms 131428 KB Output is correct
34 Correct 68 ms 131404 KB Output is correct
35 Correct 68 ms 131412 KB Output is correct
36 Correct 66 ms 130380 KB Output is correct
37 Correct 72 ms 133004 KB Output is correct
38 Correct 77 ms 132476 KB Output is correct
39 Correct 72 ms 132788 KB Output is correct
40 Correct 75 ms 132732 KB Output is correct
41 Correct 87 ms 132776 KB Output is correct
42 Correct 70 ms 130804 KB Output is correct
43 Correct 71 ms 130880 KB Output is correct
44 Correct 68 ms 130804 KB Output is correct
45 Correct 75 ms 135244 KB Output is correct
46 Correct 75 ms 135172 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 130044 KB Output is correct
2 Correct 66 ms 130140 KB Output is correct
3 Correct 74 ms 130032 KB Output is correct
4 Correct 70 ms 130196 KB Output is correct
5 Correct 63 ms 130132 KB Output is correct
6 Correct 64 ms 130140 KB Output is correct
7 Correct 67 ms 130032 KB Output is correct
8 Correct 67 ms 130128 KB Output is correct
9 Correct 65 ms 130128 KB Output is correct
10 Correct 62 ms 130124 KB Output is correct
11 Correct 60 ms 130164 KB Output is correct
12 Correct 65 ms 130096 KB Output is correct
13 Correct 64 ms 130084 KB Output is correct
14 Correct 67 ms 130124 KB Output is correct
15 Correct 67 ms 130104 KB Output is correct
16 Correct 63 ms 130124 KB Output is correct
17 Correct 63 ms 130272 KB Output is correct
18 Correct 63 ms 130372 KB Output is correct
19 Correct 66 ms 130264 KB Output is correct
20 Correct 66 ms 130356 KB Output is correct
21 Correct 73 ms 130148 KB Output is correct
22 Correct 62 ms 130360 KB Output is correct
23 Correct 60 ms 130308 KB Output is correct
24 Correct 63 ms 130384 KB Output is correct
25 Correct 67 ms 130288 KB Output is correct
26 Correct 62 ms 130308 KB Output is correct
27 Correct 64 ms 130352 KB Output is correct
28 Correct 67 ms 130548 KB Output is correct
29 Correct 64 ms 130816 KB Output is correct
30 Correct 64 ms 130456 KB Output is correct
31 Correct 65 ms 130620 KB Output is correct
32 Correct 63 ms 130500 KB Output is correct
33 Correct 70 ms 131412 KB Output is correct
34 Correct 75 ms 131360 KB Output is correct
35 Correct 80 ms 131532 KB Output is correct
36 Correct 65 ms 130372 KB Output is correct
37 Correct 72 ms 133196 KB Output is correct
38 Correct 71 ms 132364 KB Output is correct
39 Correct 75 ms 132864 KB Output is correct
40 Correct 86 ms 132736 KB Output is correct
41 Correct 78 ms 132772 KB Output is correct
42 Correct 80 ms 130812 KB Output is correct
43 Correct 73 ms 130812 KB Output is correct
44 Correct 69 ms 130720 KB Output is correct
45 Correct 71 ms 135200 KB Output is correct
46 Correct 76 ms 135196 KB Output is correct
47 Correct 95 ms 140648 KB Output is correct
48 Correct 79 ms 133920 KB Output is correct
49 Correct 71 ms 133208 KB Output is correct
50 Correct 73 ms 133256 KB Output is correct
51 Correct 90 ms 135616 KB Output is correct
52 Correct 100 ms 135868 KB Output is correct
53 Correct 79 ms 132684 KB Output is correct
54 Correct 78 ms 132084 KB Output is correct
55 Correct 72 ms 132068 KB Output is correct
56 Correct 78 ms 132976 KB Output is correct
57 Correct 201 ms 187776 KB Output is correct
58 Correct 84 ms 132768 KB Output is correct
59 Correct 72 ms 133516 KB Output is correct
60 Correct 73 ms 134132 KB Output is correct
61 Correct 81 ms 133260 KB Output is correct
62 Correct 89 ms 137060 KB Output is correct
63 Correct 107 ms 154360 KB Output is correct
64 Correct 112 ms 162260 KB Output is correct
65 Correct 136 ms 168360 KB Output is correct
66 Correct 192 ms 199424 KB Output is correct
67 Correct 195 ms 201108 KB Output is correct