oj.uz

Submission #583215

# Submission time Handle Problem Language Result Execution time Memory
583215 2022-06-25T05:59:04 Z Justin1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 811 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct edge{
	int v, c;
};
 
const int maxpow = 173;
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 84 ms 130168 KB Output is correct
2 Correct 79 ms 130108 KB Output is correct
3 Correct 74 ms 130084 KB Output is correct
4 Correct 75 ms 130128 KB Output is correct
5 Correct 78 ms 130104 KB Output is correct
6 Correct 82 ms 130212 KB Output is correct
7 Correct 76 ms 130120 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 130168 KB Output is correct
2 Correct 71 ms 130064 KB Output is correct
3 Correct 76 ms 130112 KB Output is correct
4 Correct 77 ms 130120 KB Output is correct
5 Correct 81 ms 130192 KB Output is correct
6 Correct 72 ms 130192 KB Output is correct
7 Correct 72 ms 130124 KB Output is correct
8 Correct 80 ms 130260 KB Output is correct
9 Correct 81 ms 130512 KB Output is correct
10 Correct 79 ms 130736 KB Output is correct
11 Correct 74 ms 130740 KB Output is correct
12 Correct 74 ms 130704 KB Output is correct
13 Correct 79 ms 130772 KB Output is correct
14 Correct 76 ms 130748 KB Output is correct
15 Correct 78 ms 130780 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 130124 KB Output is correct
2 Correct 84 ms 130108 KB Output is correct
3 Correct 79 ms 130124 KB Output is correct
4 Correct 72 ms 130124 KB Output is correct
5 Correct 92 ms 130216 KB Output is correct
6 Correct 83 ms 130136 KB Output is correct
7 Correct 81 ms 130108 KB Output is correct
8 Correct 76 ms 130444 KB Output is correct
9 Correct 83 ms 130512 KB Output is correct
10 Correct 92 ms 130720 KB Output is correct
11 Correct 76 ms 130780 KB Output is correct
12 Correct 75 ms 130736 KB Output is correct
13 Correct 75 ms 130864 KB Output is correct
14 Correct 80 ms 130800 KB Output is correct
15 Correct 79 ms 130792 KB Output is correct
16 Correct 94 ms 131688 KB Output is correct
17 Correct 95 ms 136336 KB Output is correct
18 Correct 137 ms 145180 KB Output is correct
19 Correct 137 ms 147500 KB Output is correct
20 Correct 145 ms 147568 KB Output is correct
21 Correct 86 ms 133148 KB Output is correct
22 Correct 125 ms 145568 KB Output is correct
23 Correct 142 ms 143836 KB Output is correct
24 Correct 154 ms 146676 KB Output is correct
25 Correct 140 ms 147532 KB Output is correct
26 Correct 144 ms 147604 KB Output is correct
27 Correct 149 ms 147580 KB Output is correct
28 Correct 148 ms 147584 KB Output is correct
29 Correct 153 ms 147700 KB Output is correct
30 Correct 155 ms 147528 KB Output is correct
31 Correct 152 ms 147640 KB Output is correct
32 Correct 147 ms 147600 KB Output is correct
33 Correct 151 ms 148004 KB Output is correct
34 Correct 146 ms 148044 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 130084 KB Output is correct
2 Correct 74 ms 130092 KB Output is correct
3 Correct 76 ms 130252 KB Output is correct
4 Correct 76 ms 130108 KB Output is correct
5 Correct 75 ms 130156 KB Output is correct
6 Correct 76 ms 130152 KB Output is correct
7 Correct 74 ms 130212 KB Output is correct
8 Correct 86 ms 130332 KB Output is correct
9 Correct 84 ms 130424 KB Output is correct
10 Correct 75 ms 130700 KB Output is correct
11 Correct 73 ms 130772 KB Output is correct
12 Correct 76 ms 130764 KB Output is correct
13 Correct 80 ms 130784 KB Output is correct
14 Correct 88 ms 130848 KB Output is correct
15 Correct 73 ms 130864 KB Output is correct
16 Correct 77 ms 131520 KB Output is correct
17 Correct 97 ms 136332 KB Output is correct
18 Correct 124 ms 145168 KB Output is correct
19 Correct 145 ms 147560 KB Output is correct
20 Correct 158 ms 147588 KB Output is correct
21 Correct 100 ms 133136 KB Output is correct
22 Correct 134 ms 145480 KB Output is correct
23 Correct 130 ms 143908 KB Output is correct
24 Correct 143 ms 146700 KB Output is correct
25 Correct 169 ms 147544 KB Output is correct
26 Correct 141 ms 147556 KB Output is correct
27 Correct 136 ms 147532 KB Output is correct
28 Correct 138 ms 147660 KB Output is correct
29 Correct 170 ms 147768 KB Output is correct
30 Correct 166 ms 147492 KB Output is correct
31 Correct 139 ms 147684 KB Output is correct
32 Correct 145 ms 147552 KB Output is correct
33 Correct 157 ms 148008 KB Output is correct
34 Correct 165 ms 148016 KB Output is correct
35 Correct 131 ms 142984 KB Output is correct
36 Correct 105 ms 139380 KB Output is correct
37 Correct 176 ms 148056 KB Output is correct
38 Correct 188 ms 148428 KB Output is correct
39 Correct 159 ms 148520 KB Output is correct
40 Correct 174 ms 148424 KB Output is correct
41 Correct 179 ms 148396 KB Output is correct
42 Correct 154 ms 147760 KB Output is correct
43 Correct 145 ms 147784 KB Output is correct
44 Correct 155 ms 147724 KB Output is correct
45 Correct 199 ms 150648 KB Output is correct
46 Correct 200 ms 150564 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 130084 KB Output is correct
2 Correct 84 ms 130124 KB Output is correct
3 Correct 76 ms 130124 KB Output is correct
4 Correct 74 ms 130184 KB Output is correct
5 Correct 78 ms 130124 KB Output is correct
6 Correct 76 ms 130184 KB Output is correct
7 Correct 76 ms 130120 KB Output is correct
8 Correct 91 ms 130264 KB Output is correct
9 Correct 74 ms 130508 KB Output is correct
10 Correct 73 ms 130760 KB Output is correct
11 Correct 83 ms 130784 KB Output is correct
12 Correct 84 ms 130780 KB Output is correct
13 Correct 78 ms 130752 KB Output is correct
14 Correct 75 ms 130896 KB Output is correct
15 Correct 78 ms 130808 KB Output is correct
16 Correct 79 ms 131536 KB Output is correct
17 Correct 96 ms 136232 KB Output is correct
18 Correct 134 ms 145184 KB Output is correct
19 Correct 146 ms 147460 KB Output is correct
20 Correct 154 ms 147608 KB Output is correct
21 Correct 87 ms 133132 KB Output is correct
22 Correct 155 ms 145528 KB Output is correct
23 Correct 130 ms 143844 KB Output is correct
24 Correct 141 ms 146696 KB Output is correct
25 Correct 148 ms 147548 KB Output is correct
26 Correct 144 ms 147508 KB Output is correct
27 Correct 140 ms 147532 KB Output is correct
28 Correct 162 ms 147584 KB Output is correct
29 Correct 153 ms 147760 KB Output is correct
30 Correct 149 ms 147572 KB Output is correct
31 Correct 146 ms 147648 KB Output is correct
32 Correct 152 ms 147552 KB Output is correct
33 Correct 155 ms 147976 KB Output is correct
34 Correct 162 ms 148052 KB Output is correct
35 Correct 133 ms 143000 KB Output is correct
36 Correct 115 ms 139384 KB Output is correct
37 Correct 176 ms 148112 KB Output is correct
38 Correct 166 ms 148428 KB Output is correct
39 Correct 188 ms 148432 KB Output is correct
40 Correct 163 ms 148536 KB Output is correct
41 Correct 162 ms 148484 KB Output is correct
42 Correct 149 ms 147792 KB Output is correct
43 Correct 142 ms 147788 KB Output is correct
44 Correct 139 ms 147828 KB Output is correct
45 Correct 203 ms 150656 KB Output is correct
46 Correct 181 ms 150492 KB Output is correct
47 Correct 811 ms 245124 KB Output is correct
48 Runtime error 779 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -