oj.uz

Submission #472044

# Submission time Handle Problem Language Result Execution time Memory
472044 2021-09-12T13:33:51 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 779 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
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define lld long double
#define pii pair<int, int> 
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	const int P = 5000000;
	const int K = 180;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<vector<pii>> mp;
	vector<vector<vector<int>>> a;
	void init_(int _n, int _m) {
		n = _n, m = _m, ii = n - 1;
		s.clear();
		dis.assign(P, INF);
		mp.assign(P, vector<pii>());
		rep(i, 0, K - 1) a.push_back(vector<vector<int>>(i, vector<int>()));
	}
	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);
			}
		}
		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:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
skyscraper.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
skyscraper.cpp: In function 'int solver::solve()':
skyscraper.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 137668 KB Output is correct
2 Correct 74 ms 137596 KB Output is correct
3 Correct 73 ms 137636 KB Output is correct
4 Correct 73 ms 137584 KB Output is correct
5 Correct 81 ms 137736 KB Output is correct
6 Correct 75 ms 137668 KB Output is correct
7 Correct 73 ms 137612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 137648 KB Output is correct
2 Correct 73 ms 137676 KB Output is correct
3 Correct 77 ms 137684 KB Output is correct
4 Correct 75 ms 137624 KB Output is correct
5 Correct 77 ms 137636 KB Output is correct
6 Correct 74 ms 137668 KB Output is correct
7 Correct 74 ms 137668 KB Output is correct
8 Correct 75 ms 137700 KB Output is correct
9 Correct 84 ms 137620 KB Output is correct
10 Correct 85 ms 137672 KB Output is correct
11 Correct 75 ms 137832 KB Output is correct
12 Correct 75 ms 137656 KB Output is correct
13 Correct 75 ms 137688 KB Output is correct
14 Correct 115 ms 138060 KB Output is correct
15 Correct 77 ms 137884 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 137668 KB Output is correct
2 Correct 76 ms 137644 KB Output is correct
3 Correct 75 ms 137624 KB Output is correct
4 Correct 77 ms 137636 KB Output is correct
5 Correct 88 ms 137668 KB Output is correct
6 Correct 76 ms 137712 KB Output is correct
7 Correct 76 ms 137640 KB Output is correct
8 Correct 74 ms 137592 KB Output is correct
9 Correct 76 ms 137668 KB Output is correct
10 Correct 77 ms 137656 KB Output is correct
11 Correct 77 ms 137924 KB Output is correct
12 Correct 75 ms 137796 KB Output is correct
13 Correct 74 ms 137632 KB Output is correct
14 Correct 76 ms 137984 KB Output is correct
15 Correct 76 ms 137924 KB Output is correct
16 Correct 80 ms 137752 KB Output is correct
17 Correct 80 ms 138384 KB Output is correct
18 Correct 76 ms 137952 KB Output is correct
19 Correct 85 ms 137808 KB Output is correct
20 Correct 76 ms 137788 KB Output is correct
21 Correct 77 ms 137792 KB Output is correct
22 Correct 77 ms 137864 KB Output is correct
23 Correct 78 ms 137980 KB Output is correct
24 Correct 76 ms 138240 KB Output is correct
25 Correct 87 ms 137928 KB Output is correct
26 Correct 77 ms 138036 KB Output is correct
27 Correct 78 ms 137924 KB Output is correct
28 Correct 79 ms 138680 KB Output is correct
29 Correct 84 ms 140556 KB Output is correct
30 Correct 76 ms 138436 KB Output is correct
31 Correct 82 ms 139148 KB Output is correct
32 Correct 80 ms 138692 KB Output is correct
33 Correct 98 ms 143300 KB Output is correct
34 Correct 97 ms 143360 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 137624 KB Output is correct
2 Correct 75 ms 137668 KB Output is correct
3 Correct 84 ms 137632 KB Output is correct
4 Correct 76 ms 137624 KB Output is correct
5 Correct 76 ms 137668 KB Output is correct
6 Correct 75 ms 137636 KB Output is correct
7 Correct 75 ms 137636 KB Output is correct
8 Correct 84 ms 137672 KB Output is correct
9 Correct 77 ms 137648 KB Output is correct
10 Correct 75 ms 137756 KB Output is correct
11 Correct 78 ms 137908 KB Output is correct
12 Correct 74 ms 137668 KB Output is correct
13 Correct 74 ms 137652 KB Output is correct
14 Correct 80 ms 137948 KB Output is correct
15 Correct 75 ms 137924 KB Output is correct
16 Correct 76 ms 137848 KB Output is correct
17 Correct 77 ms 138376 KB Output is correct
18 Correct 74 ms 138008 KB Output is correct
19 Correct 88 ms 137816 KB Output is correct
20 Correct 80 ms 137768 KB Output is correct
21 Correct 75 ms 137692 KB Output is correct
22 Correct 78 ms 137924 KB Output is correct
23 Correct 77 ms 137888 KB Output is correct
24 Correct 78 ms 138224 KB Output is correct
25 Correct 81 ms 138156 KB Output is correct
26 Correct 76 ms 137992 KB Output is correct
27 Correct 77 ms 137976 KB Output is correct
28 Correct 92 ms 138792 KB Output is correct
29 Correct 87 ms 140452 KB Output is correct
30 Correct 78 ms 138612 KB Output is correct
31 Correct 79 ms 139204 KB Output is correct
32 Correct 79 ms 138692 KB Output is correct
33 Correct 98 ms 143300 KB Output is correct
34 Correct 98 ms 143300 KB Output is correct
35 Correct 100 ms 142500 KB Output is correct
36 Correct 81 ms 138420 KB Output is correct
37 Correct 123 ms 145752 KB Output is correct
38 Correct 131 ms 145208 KB Output is correct
39 Correct 123 ms 145284 KB Output is correct
40 Correct 120 ms 145220 KB Output is correct
41 Correct 124 ms 145256 KB Output is correct
42 Correct 84 ms 138300 KB Output is correct
43 Correct 80 ms 138252 KB Output is correct
44 Correct 93 ms 138128 KB Output is correct
45 Correct 228 ms 160584 KB Output is correct
46 Correct 222 ms 160496 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 137636 KB Output is correct
2 Correct 76 ms 137672 KB Output is correct
3 Correct 82 ms 137576 KB Output is correct
4 Correct 79 ms 137832 KB Output is correct
5 Correct 75 ms 137568 KB Output is correct
6 Correct 80 ms 137560 KB Output is correct
7 Correct 85 ms 137604 KB Output is correct
8 Correct 83 ms 137560 KB Output is correct
9 Correct 76 ms 137664 KB Output is correct
10 Correct 75 ms 137796 KB Output is correct
11 Correct 78 ms 137896 KB Output is correct
12 Correct 74 ms 137636 KB Output is correct
13 Correct 78 ms 137652 KB Output is correct
14 Correct 78 ms 137912 KB Output is correct
15 Correct 78 ms 137920 KB Output is correct
16 Correct 79 ms 137776 KB Output is correct
17 Correct 82 ms 138256 KB Output is correct
18 Correct 78 ms 137960 KB Output is correct
19 Correct 76 ms 137832 KB Output is correct
20 Correct 73 ms 137736 KB Output is correct
21 Correct 75 ms 137744 KB Output is correct
22 Correct 76 ms 137924 KB Output is correct
23 Correct 80 ms 137968 KB Output is correct
24 Correct 82 ms 138204 KB Output is correct
25 Correct 77 ms 137924 KB Output is correct
26 Correct 84 ms 137988 KB Output is correct
27 Correct 75 ms 137980 KB Output is correct
28 Correct 80 ms 138676 KB Output is correct
29 Correct 86 ms 140476 KB Output is correct
30 Correct 78 ms 138484 KB Output is correct
31 Correct 92 ms 139168 KB Output is correct
32 Correct 86 ms 138788 KB Output is correct
33 Correct 96 ms 143256 KB Output is correct
34 Correct 99 ms 143268 KB Output is correct
35 Correct 99 ms 142532 KB Output is correct
36 Correct 78 ms 138476 KB Output is correct
37 Correct 128 ms 145864 KB Output is correct
38 Correct 118 ms 145164 KB Output is correct
39 Correct 118 ms 145148 KB Output is correct
40 Correct 120 ms 145220 KB Output is correct
41 Correct 140 ms 145180 KB Output is correct
42 Correct 86 ms 138352 KB Output is correct
43 Correct 81 ms 138276 KB Output is correct
44 Correct 82 ms 138172 KB Output is correct
45 Correct 225 ms 160188 KB Output is correct
46 Correct 225 ms 160196 KB Output is correct
47 Correct 282 ms 172232 KB Output is correct
48 Correct 111 ms 148548 KB Output is correct
49 Correct 100 ms 144396 KB Output is correct
50 Correct 103 ms 144416 KB Output is correct
51 Correct 161 ms 152388 KB Output is correct
52 Correct 160 ms 153760 KB Output is correct
53 Correct 95 ms 141892 KB Output is correct
54 Correct 79 ms 139088 KB Output is correct
55 Correct 94 ms 140140 KB Output is correct
56 Correct 101 ms 140092 KB Output is correct
57 Correct 178 ms 157972 KB Output is correct
58 Correct 89 ms 140896 KB Output is correct
59 Correct 96 ms 142408 KB Output is correct
60 Correct 110 ms 144196 KB Output is correct
61 Correct 101 ms 142788 KB Output is correct
62 Correct 164 ms 160992 KB Output is correct
63 Correct 779 ms 244324 KB Output is correct
64 Runtime error 395 ms 262148 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -