oj.uz

Submission #472030

# Submission time Handle Problem Language Result Execution time Memory
472030 2021-09-12T13:14:20 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 88 ms 138752 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>());
		a.assign(K, vector<vector<int>>(K, vector<int>()));
	}
	void add_node(int pos, int b) {
		ii++;
		mp[pos].push_back({ii, 0});
		for(int i = pos % b - b; i >= 0; i -= b) {
			ii++, mp[ii - 1].push_back({ii, 1});
			mp[ii].push_back({i, 0});
		}
		for(int i = pos % b + b; i < n; i += b) {
			ii ++, 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];
			for(int k = j; k < n; k += i) {
				ii++;
				int id = lower_bound(all(v), k) - v.begin();
				if(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;}
      |                     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 137984 KB Output is correct
2 Correct 76 ms 137964 KB Output is correct
3 Correct 75 ms 137928 KB Output is correct
4 Correct 75 ms 138044 KB Output is correct
5 Correct 74 ms 138052 KB Output is correct
6 Correct 75 ms 138024 KB Output is correct
7 Correct 73 ms 138016 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 138028 KB Output is correct
2 Correct 74 ms 137956 KB Output is correct
3 Correct 75 ms 137944 KB Output is correct
4 Correct 75 ms 138036 KB Output is correct
5 Correct 85 ms 138028 KB Output is correct
6 Correct 74 ms 138040 KB Output is correct
7 Correct 75 ms 137944 KB Output is correct
8 Correct 76 ms 138052 KB Output is correct
9 Correct 78 ms 138004 KB Output is correct
10 Correct 77 ms 138048 KB Output is correct
11 Correct 76 ms 138436 KB Output is correct
12 Correct 77 ms 138052 KB Output is correct
13 Correct 75 ms 138068 KB Output is correct
14 Correct 75 ms 138380 KB Output is correct
15 Correct 75 ms 138304 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 138028 KB Output is correct
2 Correct 77 ms 138064 KB Output is correct
3 Correct 75 ms 137992 KB Output is correct
4 Correct 74 ms 137992 KB Output is correct
5 Correct 73 ms 137996 KB Output is correct
6 Correct 76 ms 138056 KB Output is correct
7 Correct 75 ms 138064 KB Output is correct
8 Correct 79 ms 137964 KB Output is correct
9 Correct 74 ms 138052 KB Output is correct
10 Correct 74 ms 138024 KB Output is correct
11 Correct 75 ms 138292 KB Output is correct
12 Correct 74 ms 138052 KB Output is correct
13 Correct 75 ms 137984 KB Output is correct
14 Correct 76 ms 138336 KB Output is correct
15 Correct 76 ms 138280 KB Output is correct
16 Correct 88 ms 138180 KB Output is correct
17 Incorrect 75 ms 138708 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 138036 KB Output is correct
2 Correct 79 ms 138184 KB Output is correct
3 Correct 76 ms 138016 KB Output is correct
4 Correct 79 ms 137972 KB Output is correct
5 Correct 86 ms 138052 KB Output is correct
6 Correct 74 ms 138024 KB Output is correct
7 Correct 74 ms 138012 KB Output is correct
8 Correct 74 ms 138060 KB Output is correct
9 Correct 76 ms 138044 KB Output is correct
10 Correct 87 ms 138084 KB Output is correct
11 Correct 75 ms 138224 KB Output is correct
12 Correct 75 ms 138260 KB Output is correct
13 Correct 76 ms 137996 KB Output is correct
14 Correct 75 ms 138332 KB Output is correct
15 Correct 77 ms 138292 KB Output is correct
16 Correct 74 ms 138140 KB Output is correct
17 Incorrect 77 ms 138752 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 137976 KB Output is correct
2 Correct 74 ms 137960 KB Output is correct
3 Correct 77 ms 138060 KB Output is correct
4 Correct 76 ms 138056 KB Output is correct
5 Correct 76 ms 138020 KB Output is correct
6 Correct 73 ms 137952 KB Output is correct
7 Correct 85 ms 137984 KB Output is correct
8 Correct 75 ms 138000 KB Output is correct
9 Correct 73 ms 137976 KB Output is correct
10 Correct 80 ms 138056 KB Output is correct
11 Correct 79 ms 138240 KB Output is correct
12 Correct 77 ms 137988 KB Output is correct
13 Correct 76 ms 138088 KB Output is correct
14 Correct 75 ms 138320 KB Output is correct
15 Correct 77 ms 138284 KB Output is correct
16 Correct 75 ms 138184 KB Output is correct
17 Incorrect 77 ms 138740 KB Output isn't correct
18 Halted 0 ms 0 KB -