oj.uz

Submission #472054

# Submission time Handle Problem Language Result Execution time Memory
472054 2021-09-12T14:06:43 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 342 ms 262148 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
 
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
 
#define INF 1000000000
using namespace std;
#define pii pair<int, int> 
namespace solver {
	const int P = 6000000;
	const int K = 174;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<pair<int, bool>> mp[P];
	vector<int> a[K][K];
	void init_(int _n, int _m) {
		n = _n, m = _m, ii = n - 1;
		s.clear();
		dis.assign(P, INF);
	}
	void get_new() {
		ii++;
		if(ii >= P) while(1);
	}
	void add_node(int pos, int b) {
		for(int i = pos % b; i < n; i += b) {
			get_new();
			if(i == pos) mp[i].push_back({ii, 0});
			if(i != pos % b) {
				mp[ii].push_back({ii - 1, 1});
				mp[ii - 1].push_back({ii, 1});
			}
			mp[ii].push_back({i, 0});
		}
	}
	int solve() {
		rep(i, 1, K - 1) rep(j, 0, i - 1) {
			if(!a[i][j].size()) continue;
			sort(all(a[i][j]));
			vector<int> &v = a[i][j];
			int id = -1;
			for(int k = j; k < n; k += i) {
				get_new();
				while(id + 1 < v.size() && v[id + 1] <= k) id ++;
				if(id >= 0 && v[id] == k) mp[k].push_back({ii, 0});
				if(k != j) {
					mp[ii].push_back({ii - 1, 1});
					mp[ii - 1].push_back({ii, 1});
				}
				mp[ii].push_back({k, 0});
			}
		}
		dis[st] = 0;
		deque<int> q;
		q.push_back(st);
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			for(auto i : mp[cur]) if(dis[i.first] == INF) {
				dis[i.first] = i.second + dis[cur];
				if(i.second) q.push_back(i.first);
				else q.push_front(i.first);
				if(i.first == ed) return dis[ed];
			}
		}
		return (dis[ed] == INF ? -1 : dis[ed]);
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, b, p; 
	cin >> n >> m;
	init_(n, m);
	rep(i, 0, m - 1) {
		cin >> b >> p;
		if(i == 0) st = b;
		if(i == 1) ed = b;
		if(p >= K) add_node(b, p);
		else a[p][b % p].push_back(b);
	} 
	cout << solve() << "\n";
	return 0;
}

Compilation message

skyscraper.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
skyscraper.cpp: In function 'int solver::solve()':
skyscraper.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 165316 KB Output is correct
2 Correct 88 ms 165308 KB Output is correct
3 Correct 90 ms 165336 KB Output is correct
4 Correct 86 ms 165316 KB Output is correct
5 Correct 87 ms 165316 KB Output is correct
6 Correct 89 ms 165316 KB Output is correct
7 Correct 94 ms 165316 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 165348 KB Output is correct
2 Correct 87 ms 165316 KB Output is correct
3 Correct 87 ms 165384 KB Output is correct
4 Correct 87 ms 165396 KB Output is correct
5 Correct 91 ms 165384 KB Output is correct
6 Correct 101 ms 165320 KB Output is correct
7 Correct 87 ms 165268 KB Output is correct
8 Correct 88 ms 165376 KB Output is correct
9 Correct 89 ms 165328 KB Output is correct
10 Correct 90 ms 165420 KB Output is correct
11 Correct 89 ms 165592 KB Output is correct
12 Correct 94 ms 165372 KB Output is correct
13 Correct 87 ms 165308 KB Output is correct
14 Correct 89 ms 165704 KB Output is correct
15 Correct 103 ms 165692 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 165464 KB Output is correct
2 Correct 90 ms 165300 KB Output is correct
3 Correct 89 ms 165368 KB Output is correct
4 Correct 86 ms 165392 KB Output is correct
5 Correct 85 ms 165292 KB Output is correct
6 Correct 88 ms 165320 KB Output is correct
7 Correct 87 ms 165296 KB Output is correct
8 Correct 87 ms 165444 KB Output is correct
9 Correct 97 ms 165308 KB Output is correct
10 Correct 88 ms 165480 KB Output is correct
11 Correct 91 ms 165612 KB Output is correct
12 Correct 90 ms 165384 KB Output is correct
13 Correct 87 ms 165364 KB Output is correct
14 Correct 88 ms 165672 KB Output is correct
15 Correct 89 ms 165612 KB Output is correct
16 Correct 89 ms 165560 KB Output is correct
17 Correct 91 ms 165992 KB Output is correct
18 Correct 88 ms 165708 KB Output is correct
19 Correct 88 ms 165600 KB Output is correct
20 Correct 89 ms 165464 KB Output is correct
21 Correct 89 ms 165436 KB Output is correct
22 Correct 89 ms 165660 KB Output is correct
23 Correct 92 ms 165636 KB Output is correct
24 Correct 90 ms 165948 KB Output is correct
25 Correct 103 ms 165632 KB Output is correct
26 Correct 94 ms 165708 KB Output is correct
27 Correct 90 ms 165772 KB Output is correct
28 Correct 94 ms 166432 KB Output is correct
29 Correct 126 ms 168260 KB Output is correct
30 Correct 93 ms 166132 KB Output is correct
31 Correct 94 ms 166844 KB Output is correct
32 Correct 93 ms 166484 KB Output is correct
33 Correct 131 ms 170948 KB Output is correct
34 Correct 109 ms 171000 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 165324 KB Output is correct
2 Correct 92 ms 165364 KB Output is correct
3 Correct 88 ms 165264 KB Output is correct
4 Correct 88 ms 165288 KB Output is correct
5 Correct 87 ms 165348 KB Output is correct
6 Correct 88 ms 165328 KB Output is correct
7 Correct 88 ms 165328 KB Output is correct
8 Correct 88 ms 165388 KB Output is correct
9 Correct 90 ms 165348 KB Output is correct
10 Correct 88 ms 165480 KB Output is correct
11 Correct 88 ms 165572 KB Output is correct
12 Correct 91 ms 165352 KB Output is correct
13 Correct 87 ms 165316 KB Output is correct
14 Correct 89 ms 165608 KB Output is correct
15 Correct 89 ms 165700 KB Output is correct
16 Correct 95 ms 165500 KB Output is correct
17 Correct 90 ms 166044 KB Output is correct
18 Correct 97 ms 165700 KB Output is correct
19 Correct 93 ms 165528 KB Output is correct
20 Correct 88 ms 165468 KB Output is correct
21 Correct 88 ms 165436 KB Output is correct
22 Correct 90 ms 165660 KB Output is correct
23 Correct 90 ms 165804 KB Output is correct
24 Correct 93 ms 165880 KB Output is correct
25 Correct 91 ms 165700 KB Output is correct
26 Correct 110 ms 165728 KB Output is correct
27 Correct 91 ms 165612 KB Output is correct
28 Correct 93 ms 166404 KB Output is correct
29 Correct 100 ms 168200 KB Output is correct
30 Correct 95 ms 166216 KB Output is correct
31 Correct 107 ms 166896 KB Output is correct
32 Correct 92 ms 166468 KB Output is correct
33 Correct 113 ms 171068 KB Output is correct
34 Correct 111 ms 170964 KB Output is correct
35 Correct 111 ms 170052 KB Output is correct
36 Correct 97 ms 166176 KB Output is correct
37 Correct 130 ms 173392 KB Output is correct
38 Correct 122 ms 172688 KB Output is correct
39 Correct 124 ms 172604 KB Output is correct
40 Correct 118 ms 172520 KB Output is correct
41 Correct 126 ms 172608 KB Output is correct
42 Correct 97 ms 165932 KB Output is correct
43 Correct 94 ms 165828 KB Output is correct
44 Correct 97 ms 165580 KB Output is correct
45 Correct 239 ms 187924 KB Output is correct
46 Correct 231 ms 188100 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 165388 KB Output is correct
2 Correct 91 ms 165272 KB Output is correct
3 Correct 87 ms 165300 KB Output is correct
4 Correct 88 ms 165312 KB Output is correct
5 Correct 89 ms 165328 KB Output is correct
6 Correct 90 ms 165392 KB Output is correct
7 Correct 91 ms 165348 KB Output is correct
8 Correct 102 ms 165292 KB Output is correct
9 Correct 87 ms 165328 KB Output is correct
10 Correct 89 ms 165464 KB Output is correct
11 Correct 91 ms 165572 KB Output is correct
12 Correct 91 ms 165408 KB Output is correct
13 Correct 100 ms 165316 KB Output is correct
14 Correct 88 ms 165676 KB Output is correct
15 Correct 92 ms 165620 KB Output is correct
16 Correct 103 ms 165568 KB Output is correct
17 Correct 93 ms 166048 KB Output is correct
18 Correct 90 ms 165712 KB Output is correct
19 Correct 90 ms 165564 KB Output is correct
20 Correct 94 ms 165552 KB Output is correct
21 Correct 98 ms 165512 KB Output is correct
22 Correct 88 ms 165584 KB Output is correct
23 Correct 88 ms 165704 KB Output is correct
24 Correct 91 ms 165884 KB Output is correct
25 Correct 89 ms 165736 KB Output is correct
26 Correct 95 ms 165700 KB Output is correct
27 Correct 88 ms 165652 KB Output is correct
28 Correct 91 ms 166492 KB Output is correct
29 Correct 98 ms 168240 KB Output is correct
30 Correct 90 ms 166160 KB Output is correct
31 Correct 95 ms 166852 KB Output is correct
32 Correct 103 ms 166468 KB Output is correct
33 Correct 110 ms 170964 KB Output is correct
34 Correct 108 ms 171008 KB Output is correct
35 Correct 117 ms 170052 KB Output is correct
36 Correct 104 ms 166116 KB Output is correct
37 Correct 120 ms 173296 KB Output is correct
38 Correct 123 ms 172652 KB Output is correct
39 Correct 121 ms 172640 KB Output is correct
40 Correct 119 ms 172636 KB Output is correct
41 Correct 119 ms 172732 KB Output is correct
42 Correct 95 ms 165796 KB Output is correct
43 Correct 96 ms 165752 KB Output is correct
44 Correct 97 ms 165572 KB Output is correct
45 Correct 251 ms 188084 KB Output is correct
46 Correct 210 ms 187852 KB Output is correct
47 Correct 205 ms 199904 KB Output is correct
48 Correct 130 ms 176196 KB Output is correct
49 Correct 114 ms 172076 KB Output is correct
50 Correct 128 ms 172112 KB Output is correct
51 Correct 149 ms 180072 KB Output is correct
52 Correct 187 ms 181380 KB Output is correct
53 Correct 107 ms 169708 KB Output is correct
54 Correct 95 ms 166684 KB Output is correct
55 Correct 99 ms 167948 KB Output is correct
56 Correct 106 ms 167748 KB Output is correct
57 Correct 148 ms 185736 KB Output is correct
58 Correct 107 ms 168608 KB Output is correct
59 Correct 110 ms 170044 KB Output is correct
60 Correct 113 ms 171832 KB Output is correct
61 Correct 109 ms 170496 KB Output is correct
62 Correct 183 ms 188652 KB Output is correct
63 Runtime error 342 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -