oj.uz

Submission #472058

# Submission time Handle Problem Language Result Execution time Memory
472058 2021-09-12T14:22:48 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 962 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 = 4000000;
	const int K = 200;
	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) exit(0);
	}
	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 61 ms 110828 KB Output is correct
2 Correct 59 ms 110788 KB Output is correct
3 Correct 62 ms 110824 KB Output is correct
4 Correct 61 ms 110756 KB Output is correct
5 Correct 59 ms 110804 KB Output is correct
6 Correct 60 ms 110784 KB Output is correct
7 Correct 64 ms 110868 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 110724 KB Output is correct
2 Correct 59 ms 110828 KB Output is correct
3 Correct 59 ms 110788 KB Output is correct
4 Correct 59 ms 110820 KB Output is correct
5 Correct 58 ms 110728 KB Output is correct
6 Correct 65 ms 110732 KB Output is correct
7 Correct 59 ms 110804 KB Output is correct
8 Correct 60 ms 110768 KB Output is correct
9 Correct 59 ms 110792 KB Output is correct
10 Correct 60 ms 110844 KB Output is correct
11 Correct 67 ms 111052 KB Output is correct
12 Correct 62 ms 110744 KB Output is correct
13 Correct 67 ms 110812 KB Output is correct
14 Correct 67 ms 111136 KB Output is correct
15 Correct 61 ms 111092 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 110816 KB Output is correct
2 Correct 60 ms 110748 KB Output is correct
3 Correct 69 ms 110724 KB Output is correct
4 Correct 60 ms 110812 KB Output is correct
5 Correct 60 ms 110728 KB Output is correct
6 Correct 59 ms 110816 KB Output is correct
7 Correct 72 ms 110792 KB Output is correct
8 Correct 61 ms 110712 KB Output is correct
9 Correct 61 ms 110768 KB Output is correct
10 Correct 61 ms 110868 KB Output is correct
11 Correct 61 ms 111040 KB Output is correct
12 Correct 61 ms 110816 KB Output is correct
13 Correct 59 ms 110788 KB Output is correct
14 Correct 62 ms 111140 KB Output is correct
15 Correct 64 ms 111136 KB Output is correct
16 Correct 63 ms 111028 KB Output is correct
17 Correct 62 ms 111428 KB Output is correct
18 Correct 61 ms 111148 KB Output is correct
19 Correct 61 ms 110948 KB Output is correct
20 Correct 63 ms 111000 KB Output is correct
21 Correct 60 ms 110888 KB Output is correct
22 Correct 68 ms 110988 KB Output is correct
23 Correct 69 ms 111140 KB Output is correct
24 Correct 70 ms 111300 KB Output is correct
25 Correct 62 ms 111172 KB Output is correct
26 Correct 61 ms 111144 KB Output is correct
27 Correct 62 ms 111104 KB Output is correct
28 Correct 67 ms 111808 KB Output is correct
29 Correct 74 ms 113640 KB Output is correct
30 Correct 60 ms 111588 KB Output is correct
31 Correct 67 ms 112280 KB Output is correct
32 Correct 65 ms 111928 KB Output is correct
33 Correct 82 ms 116424 KB Output is correct
34 Correct 83 ms 116448 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 110764 KB Output is correct
2 Correct 60 ms 110712 KB Output is correct
3 Correct 60 ms 110724 KB Output is correct
4 Correct 60 ms 110748 KB Output is correct
5 Correct 60 ms 110756 KB Output is correct
6 Correct 61 ms 110788 KB Output is correct
7 Correct 72 ms 110756 KB Output is correct
8 Correct 60 ms 110804 KB Output is correct
9 Correct 68 ms 110800 KB Output is correct
10 Correct 60 ms 110872 KB Output is correct
11 Correct 60 ms 111044 KB Output is correct
12 Correct 60 ms 110760 KB Output is correct
13 Correct 59 ms 110788 KB Output is correct
14 Correct 59 ms 111136 KB Output is correct
15 Correct 62 ms 111044 KB Output is correct
16 Correct 60 ms 110956 KB Output is correct
17 Correct 63 ms 111496 KB Output is correct
18 Correct 61 ms 111044 KB Output is correct
19 Correct 60 ms 110944 KB Output is correct
20 Correct 63 ms 110960 KB Output is correct
21 Correct 61 ms 110864 KB Output is correct
22 Correct 60 ms 111016 KB Output is correct
23 Correct 72 ms 111032 KB Output is correct
24 Correct 63 ms 111320 KB Output is correct
25 Correct 64 ms 111172 KB Output is correct
26 Correct 68 ms 111168 KB Output is correct
27 Correct 62 ms 111048 KB Output is correct
28 Correct 63 ms 111888 KB Output is correct
29 Correct 69 ms 113604 KB Output is correct
30 Correct 62 ms 111624 KB Output is correct
31 Correct 66 ms 112372 KB Output is correct
32 Correct 67 ms 111928 KB Output is correct
33 Correct 82 ms 116420 KB Output is correct
34 Correct 80 ms 116472 KB Output is correct
35 Correct 82 ms 115404 KB Output is correct
36 Correct 63 ms 111608 KB Output is correct
37 Correct 90 ms 118844 KB Output is correct
38 Correct 100 ms 118160 KB Output is correct
39 Correct 91 ms 118084 KB Output is correct
40 Correct 88 ms 118084 KB Output is correct
41 Correct 91 ms 117992 KB Output is correct
42 Correct 66 ms 111300 KB Output is correct
43 Correct 66 ms 111144 KB Output is correct
44 Correct 74 ms 111004 KB Output is correct
45 Correct 216 ms 133488 KB Output is correct
46 Correct 189 ms 133556 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 110796 KB Output is correct
2 Correct 67 ms 110788 KB Output is correct
3 Correct 62 ms 110808 KB Output is correct
4 Correct 61 ms 110772 KB Output is correct
5 Correct 61 ms 110788 KB Output is correct
6 Correct 62 ms 110768 KB Output is correct
7 Correct 65 ms 110816 KB Output is correct
8 Correct 62 ms 110788 KB Output is correct
9 Correct 60 ms 110752 KB Output is correct
10 Correct 59 ms 110916 KB Output is correct
11 Correct 61 ms 111016 KB Output is correct
12 Correct 59 ms 110788 KB Output is correct
13 Correct 59 ms 110780 KB Output is correct
14 Correct 65 ms 111120 KB Output is correct
15 Correct 63 ms 111100 KB Output is correct
16 Correct 61 ms 110916 KB Output is correct
17 Correct 62 ms 111436 KB Output is correct
18 Correct 61 ms 111044 KB Output is correct
19 Correct 61 ms 111044 KB Output is correct
20 Correct 63 ms 111008 KB Output is correct
21 Correct 61 ms 110932 KB Output is correct
22 Correct 60 ms 111044 KB Output is correct
23 Correct 60 ms 111036 KB Output is correct
24 Correct 62 ms 111384 KB Output is correct
25 Correct 64 ms 111200 KB Output is correct
26 Correct 65 ms 111196 KB Output is correct
27 Correct 60 ms 111100 KB Output is correct
28 Correct 67 ms 111808 KB Output is correct
29 Correct 70 ms 113620 KB Output is correct
30 Correct 62 ms 111596 KB Output is correct
31 Correct 64 ms 112320 KB Output is correct
32 Correct 66 ms 111824 KB Output is correct
33 Correct 89 ms 116492 KB Output is correct
34 Correct 83 ms 116420 KB Output is correct
35 Correct 83 ms 115396 KB Output is correct
36 Correct 64 ms 111616 KB Output is correct
37 Correct 101 ms 118852 KB Output is correct
38 Correct 98 ms 118084 KB Output is correct
39 Correct 88 ms 118076 KB Output is correct
40 Correct 89 ms 117988 KB Output is correct
41 Correct 93 ms 118096 KB Output is correct
42 Correct 68 ms 111264 KB Output is correct
43 Correct 72 ms 111176 KB Output is correct
44 Correct 65 ms 111080 KB Output is correct
45 Correct 224 ms 133460 KB Output is correct
46 Correct 188 ms 133464 KB Output is correct
47 Correct 181 ms 145392 KB Output is correct
48 Correct 103 ms 121628 KB Output is correct
49 Correct 85 ms 117448 KB Output is correct
50 Correct 83 ms 117488 KB Output is correct
51 Correct 133 ms 125528 KB Output is correct
52 Correct 151 ms 126872 KB Output is correct
53 Correct 82 ms 115096 KB Output is correct
54 Correct 64 ms 112196 KB Output is correct
55 Correct 66 ms 113296 KB Output is correct
56 Correct 74 ms 113224 KB Output is correct
57 Correct 120 ms 131092 KB Output is correct
58 Correct 78 ms 113984 KB Output is correct
59 Correct 78 ms 115484 KB Output is correct
60 Correct 86 ms 117184 KB Output is correct
61 Correct 82 ms 115964 KB Output is correct
62 Correct 153 ms 134172 KB Output is correct
63 Correct 815 ms 217616 KB Output is correct
64 Correct 962 ms 241792 KB Output is correct
65 Runtime error 462 ms 262148 KB Execution killed with signal 9
66 Halted 0 ms 0 KB -