oj.uz

Submission #472053

# Submission time Handle Problem Language Result Execution time Memory
472053 2021-09-12T14:02:09 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 103 ms 166068 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});
			else if(i > pos % b) 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:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 165352 KB Output is correct
2 Correct 89 ms 165344 KB Output is correct
3 Correct 86 ms 165384 KB Output is correct
4 Correct 86 ms 165320 KB Output is correct
5 Correct 89 ms 165360 KB Output is correct
6 Correct 87 ms 165340 KB Output is correct
7 Correct 91 ms 165316 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 165456 KB Output is correct
2 Correct 98 ms 165280 KB Output is correct
3 Correct 95 ms 165480 KB Output is correct
4 Correct 98 ms 165308 KB Output is correct
5 Correct 87 ms 165340 KB Output is correct
6 Correct 93 ms 165284 KB Output is correct
7 Correct 88 ms 165352 KB Output is correct
8 Correct 86 ms 165328 KB Output is correct
9 Correct 90 ms 165424 KB Output is correct
10 Correct 96 ms 165376 KB Output is correct
11 Correct 90 ms 165544 KB Output is correct
12 Correct 90 ms 165312 KB Output is correct
13 Correct 90 ms 165316 KB Output is correct
14 Correct 99 ms 165760 KB Output is correct
15 Correct 94 ms 165632 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 165332 KB Output is correct
2 Correct 88 ms 165296 KB Output is correct
3 Correct 89 ms 165304 KB Output is correct
4 Correct 92 ms 165352 KB Output is correct
5 Correct 92 ms 165332 KB Output is correct
6 Correct 86 ms 165356 KB Output is correct
7 Correct 88 ms 165308 KB Output is correct
8 Correct 103 ms 165292 KB Output is correct
9 Correct 89 ms 165288 KB Output is correct
10 Correct 87 ms 165448 KB Output is correct
11 Correct 91 ms 165580 KB Output is correct
12 Correct 102 ms 165364 KB Output is correct
13 Correct 87 ms 165284 KB Output is correct
14 Correct 96 ms 165616 KB Output is correct
15 Correct 91 ms 165708 KB Output is correct
16 Correct 93 ms 165576 KB Output is correct
17 Incorrect 91 ms 166044 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 165316 KB Output is correct
2 Correct 88 ms 165360 KB Output is correct
3 Correct 89 ms 165360 KB Output is correct
4 Correct 90 ms 165320 KB Output is correct
5 Correct 99 ms 165316 KB Output is correct
6 Correct 89 ms 165304 KB Output is correct
7 Correct 88 ms 165376 KB Output is correct
8 Correct 94 ms 165352 KB Output is correct
9 Correct 96 ms 165316 KB Output is correct
10 Correct 89 ms 165444 KB Output is correct
11 Correct 89 ms 165516 KB Output is correct
12 Correct 90 ms 165420 KB Output is correct
13 Correct 87 ms 165388 KB Output is correct
14 Correct 91 ms 165672 KB Output is correct
15 Correct 89 ms 165672 KB Output is correct
16 Correct 93 ms 165520 KB Output is correct
17 Incorrect 90 ms 166068 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 165388 KB Output is correct
2 Correct 87 ms 165272 KB Output is correct
3 Correct 92 ms 165316 KB Output is correct
4 Correct 89 ms 165384 KB Output is correct
5 Correct 88 ms 165376 KB Output is correct
6 Correct 87 ms 165356 KB Output is correct
7 Correct 88 ms 165272 KB Output is correct
8 Correct 88 ms 165280 KB Output is correct
9 Correct 87 ms 165368 KB Output is correct
10 Correct 87 ms 165356 KB Output is correct
11 Correct 89 ms 165576 KB Output is correct
12 Correct 85 ms 165316 KB Output is correct
13 Correct 92 ms 165340 KB Output is correct
14 Correct 88 ms 165708 KB Output is correct
15 Correct 89 ms 165632 KB Output is correct
16 Correct 92 ms 165544 KB Output is correct
17 Incorrect 94 ms 165956 KB Output isn't correct
18 Halted 0 ms 0 KB -