#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#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 lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#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
#define x first
#define y second
namespace solver {
int n, m, s, t, ii;
const int P = 180, mx = 10000000;
vector<pii> mp[mx], a;
vector<int> v[P + 1][P + 1];
vector<int> dis;
void init_(int _n, int _m) {
ii = _n;
n = _n, m = _m;
a.clear();
dis.assign(mx, INF);
}
void solve() {
for(auto i : a) {
int st = i.y % i.x;
for(int j = st; j < n; j += i.x) {
ii++;
if(j != st) mp[ii].push_back({ii - 1, 1});
if(j + i.x < n) mp[ii].push_back({ii + 1, 1});
if(j == i.y) mp[j].push_back({ii, 0});
mp[ii].push_back({j, 0});
}
}
rep(i, 1, P) rep(j, 0, i - 1) {
sort(all(v[i][j]));
if(!v[i][j].size()) continue;
int cur = 0;
for(int k = j; k < n; k += i) {
ii++;
if(k != j) mp[ii].push_back({ii - 1, 1});
if(k + i < n) mp[ii].push_back({ii + 1, 1});
if(cur < v[i][j].size() &&
v[i][j][cur] == k) mp[k].push_back({ii, 0}), cur++;
mp[ii].push_back({k, 0});
}
}
dis[s] = 0;
deque<int> q;
q.push_back(s);
while(q.size()) {
int cur = q.front();
q.pop_front();
if(cur == t) {
cout << dis[cur] << "\n";
return;
}
for(auto i : mp[cur]) {
if(dis[i.x] != INF) continue;
dis[i.x] = dis[cur] + i.y;
if(i.y) q.push_back(i.x);
else q.push_front(i.x);
}
}
cout << "-1\n";
return;
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, m;
cin >> n >> m;
init_(n, m);
rep(i, 0, m - 1) {
int b, p;
cin >> b >> p;
if(i == 0) s = b;
if(i == 1) t = b;
if(p <= P) v[p][b % p].push_back(b);
else a.push_back({p, b});
}
solve();
return 0;
}
Compilation message
skyscraper.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
5 | #pragma loop-opt(on)
|
skyscraper.cpp:19:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
skyscraper.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
skyscraper.cpp: In function 'void solver::solve()':
skyscraper.cpp:59:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if(cur < v[i][j].size() &&
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
109 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
