oj.uz

Submission #472052

# Submission time Handle Problem Language Result Execution time Memory
472052 2021-09-12T13:55:23 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 109 ms 168900 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 = 6000000;
	const int K = 174;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<vector<pair<short, bool>>> mp;
	vector<vector<vector<short>>> a;
	void init_(int _n, int _m) {
		n = _n, m = _m, ii = n - 1;
		s.clear();
		dis.assign(P, INF);
		mp.assign(P, vector<pair<short, bool>>());
		rep(i, 0, K - 1) a.push_back(vector<vector<short>>(i, vector<short>()));
	}
	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<short> &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: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<short 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 89 ms 164932 KB Output is correct
2 Correct 89 ms 164980 KB Output is correct
3 Correct 89 ms 165020 KB Output is correct
4 Correct 92 ms 165036 KB Output is correct
5 Correct 92 ms 165008 KB Output is correct
6 Correct 92 ms 165052 KB Output is correct
7 Correct 90 ms 164936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 164972 KB Output is correct
2 Correct 90 ms 165152 KB Output is correct
3 Correct 89 ms 165060 KB Output is correct
4 Correct 90 ms 164936 KB Output is correct
5 Correct 91 ms 165044 KB Output is correct
6 Correct 91 ms 165024 KB Output is correct
7 Correct 89 ms 164928 KB Output is correct
8 Correct 89 ms 165116 KB Output is correct
9 Correct 89 ms 165048 KB Output is correct
10 Correct 97 ms 165100 KB Output is correct
11 Correct 92 ms 165220 KB Output is correct
12 Correct 90 ms 165060 KB Output is correct
13 Correct 92 ms 165016 KB Output is correct
14 Correct 91 ms 165292 KB Output is correct
15 Correct 91 ms 165300 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 164956 KB Output is correct
2 Correct 92 ms 165080 KB Output is correct
3 Correct 95 ms 165048 KB Output is correct
4 Correct 89 ms 165000 KB Output is correct
5 Correct 95 ms 164948 KB Output is correct
6 Correct 90 ms 165004 KB Output is correct
7 Correct 89 ms 164960 KB Output is correct
8 Correct 95 ms 164992 KB Output is correct
9 Correct 91 ms 165056 KB Output is correct
10 Correct 90 ms 165172 KB Output is correct
11 Correct 92 ms 165136 KB Output is correct
12 Correct 91 ms 165060 KB Output is correct
13 Correct 92 ms 164968 KB Output is correct
14 Correct 94 ms 165360 KB Output is correct
15 Correct 91 ms 165236 KB Output is correct
16 Correct 89 ms 165180 KB Output is correct
17 Correct 92 ms 165540 KB Output is correct
18 Correct 90 ms 165248 KB Output is correct
19 Correct 90 ms 165104 KB Output is correct
20 Correct 92 ms 165224 KB Output is correct
21 Correct 93 ms 165032 KB Output is correct
22 Correct 100 ms 165176 KB Output is correct
23 Correct 93 ms 165188 KB Output is correct
24 Correct 93 ms 165392 KB Output is correct
25 Correct 94 ms 165308 KB Output is correct
26 Correct 91 ms 165312 KB Output is correct
27 Correct 91 ms 165268 KB Output is correct
28 Correct 93 ms 165764 KB Output is correct
29 Correct 98 ms 166984 KB Output is correct
30 Correct 93 ms 165592 KB Output is correct
31 Correct 96 ms 166032 KB Output is correct
32 Correct 93 ms 165760 KB Output is correct
33 Incorrect 109 ms 168900 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 164960 KB Output is correct
2 Correct 90 ms 165004 KB Output is correct
3 Correct 89 ms 165056 KB Output is correct
4 Correct 88 ms 165012 KB Output is correct
5 Correct 89 ms 164968 KB Output is correct
6 Correct 90 ms 164972 KB Output is correct
7 Correct 90 ms 165056 KB Output is correct
8 Correct 89 ms 165044 KB Output is correct
9 Correct 89 ms 164980 KB Output is correct
10 Correct 88 ms 165120 KB Output is correct
11 Correct 99 ms 165352 KB Output is correct
12 Correct 93 ms 165016 KB Output is correct
13 Correct 90 ms 165024 KB Output is correct
14 Correct 93 ms 165232 KB Output is correct
15 Correct 91 ms 165320 KB Output is correct
16 Correct 89 ms 165200 KB Output is correct
17 Correct 95 ms 165444 KB Output is correct
18 Correct 92 ms 165184 KB Output is correct
19 Correct 88 ms 165132 KB Output is correct
20 Correct 91 ms 165076 KB Output is correct
21 Correct 91 ms 165060 KB Output is correct
22 Correct 91 ms 165196 KB Output is correct
23 Correct 92 ms 165392 KB Output is correct
24 Correct 94 ms 165380 KB Output is correct
25 Correct 91 ms 165320 KB Output is correct
26 Correct 90 ms 165280 KB Output is correct
27 Correct 96 ms 165208 KB Output is correct
28 Correct 96 ms 165828 KB Output is correct
29 Correct 99 ms 166976 KB Output is correct
30 Correct 92 ms 165572 KB Output is correct
31 Correct 94 ms 166108 KB Output is correct
32 Correct 93 ms 165724 KB Output is correct
33 Incorrect 107 ms 168900 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 164984 KB Output is correct
2 Correct 89 ms 164960 KB Output is correct
3 Correct 90 ms 164984 KB Output is correct
4 Correct 93 ms 165052 KB Output is correct
5 Correct 89 ms 165008 KB Output is correct
6 Correct 90 ms 164932 KB Output is correct
7 Correct 89 ms 164964 KB Output is correct
8 Correct 91 ms 164932 KB Output is correct
9 Correct 90 ms 165064 KB Output is correct
10 Correct 94 ms 165268 KB Output is correct
11 Correct 90 ms 165188 KB Output is correct
12 Correct 89 ms 164952 KB Output is correct
13 Correct 89 ms 165000 KB Output is correct
14 Correct 90 ms 165308 KB Output is correct
15 Correct 90 ms 165300 KB Output is correct
16 Correct 91 ms 165104 KB Output is correct
17 Correct 90 ms 165480 KB Output is correct
18 Correct 91 ms 165196 KB Output is correct
19 Correct 89 ms 165176 KB Output is correct
20 Correct 91 ms 165128 KB Output is correct
21 Correct 90 ms 165088 KB Output is correct
22 Correct 93 ms 165168 KB Output is correct
23 Correct 90 ms 165280 KB Output is correct
24 Correct 91 ms 165444 KB Output is correct
25 Correct 91 ms 165228 KB Output is correct
26 Correct 95 ms 165296 KB Output is correct
27 Correct 91 ms 165188 KB Output is correct
28 Correct 105 ms 165836 KB Output is correct
29 Correct 99 ms 166868 KB Output is correct
30 Correct 91 ms 165520 KB Output is correct
31 Correct 97 ms 165996 KB Output is correct
32 Correct 94 ms 165700 KB Output is correct
33 Incorrect 107 ms 168900 KB Output isn't correct
34 Halted 0 ms 0 KB -