#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define fillc(p, t, v) fill_n((t*) p, sizeof(p) / sizeof(t), v)
#define pb push_back
#define MID 269
#define O 30069
#define MAX 9690000000000ll
#define K 9999999999699ll
#define OM (O / MID + 69)
int N, M;
int B[O];
int P[O];
int TP;
vector<int> SMALL[O];
vector<int> BIG[O];
ll smallc[O][MID + 69];
bool seen1[O][MID + 69];
ll bigc[O][2 * OM + 69];
ll dp_small(int, int);
ll dp_big(int, int);
ll dp_small(int pos, int step) {
ll& ans = smallc[pos][step];
if(ans != -2) return ans;
ans = K;
ll a = ans;
if(pos == TP) return ans = 0;
for(int j : SMALL[pos]) {
a = min(a, dp_small(B[j], P[j]));
}
for(int j : BIG[pos]) {
a = min(a, dp_big(j, OM));
}
if(pos - step >= 0) {
a = min(a, 1 + dp_small(pos - step, step));
}
if(pos + step < N) {
a = min(a, 1 + dp_small(pos + step, step));
}
if(a == K) {
ans = -2;
return K;
}else{
ans = min(ans, MAX);
return ans = a;
}
}
ll dp_big(int i, int offset) {
ll& ans = bigc[i][offset];
if(ans != -2) return ans;
ans = MAX;
int pos = B[i] + (offset - OM) * P[i];
if(pos == TP) return ans = 0;
for(int j : SMALL[pos]) {
ans = min(ans, dp_small(B[j], P[j]));
}
for(int j : BIG[pos]) {
ans = min(ans, dp_big(j, OM));
}
if(pos - P[i] >= 0) {
ans = min(ans, 1 + dp_big(i, offset - 1));
}
if(pos + P[i] < N) {
ans = min(ans, 1 + dp_big(i, offset + 1));
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for(int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
if(P[i] < MID)
SMALL[B[i]].pb(i);
else
BIG[B[i]].pb(i);
}
fillc(smallc, ll, MAX);
fillc(bigc, ll, MAX);
queue<pair<int, pair<int, int>>> q;
if(P[0] < MID) {
smallc[B[0]][P[0]] = 0;
q.push({0, {B[0], P[0]}});
}else{
bigc[0][OM] = 0;
q.push({1, {0, OM}});
}
while(not q.empty()) {
auto p = q.front();
q.pop();
int pos, step;
int a, b;
int t = p.first;
a = p.second.first;
b = p.second.second;
ll dis;
if (t == 0) {
dis = smallc[a][b];
pos = a;
step = b;
}else{
dis = bigc[a][b];
pos = B[a] + (b - OM) * P[a];
step = P[a];
}
for(int j : SMALL[pos]) {
ll& c = smallc[B[j]][P[j]];
if(dis < c) {
c = dis;
q.push({0, {B[j], P[j]}});
}
}
for(int j : BIG[pos]) {
ll& c = bigc[j][OM];
if(dis < c) {
c = dis;
q.push({1, {j, OM}});
}
}
if(t == 0) {
if(pos - step >= 0) {
ll& c = smallc[pos - step][step];
if(dis + 1 < c) {
c = dis + 1;
q.push({t, {pos - step, step}});
}
}
if(pos + step < N) {
ll& c = smallc[pos + step][step];
if(dis + 1 < c) {
c = dis + 1;
q.push({t, {pos + step, step}});
}
}
}else{
if(pos - step >= 0) {
ll& c = bigc[a][b - 1];
if(dis + 1 < c) {
c = dis + 1;
q.push({t, {a, b - 1}});
}
}
if(pos + step < N) {
ll& c = bigc[a][b + 1];
if(dis + 1 < c) {
c = dis + 1;
q.push({t, {a, b + 1}});
}
}
}
}
ll ans = smallc[B[1]][P[1]];
cout << (ans >= MAX ? -1 : ans) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
182252 KB |
Output is correct |
2 |
Correct |
97 ms |
182252 KB |
Output is correct |
3 |
Correct |
96 ms |
182252 KB |
Output is correct |
4 |
Correct |
98 ms |
182252 KB |
Output is correct |
5 |
Correct |
97 ms |
182252 KB |
Output is correct |
6 |
Correct |
98 ms |
182252 KB |
Output is correct |
7 |
Correct |
98 ms |
182276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
182324 KB |
Output is correct |
2 |
Correct |
97 ms |
182416 KB |
Output is correct |
3 |
Correct |
97 ms |
182340 KB |
Output is correct |
4 |
Correct |
97 ms |
182380 KB |
Output is correct |
5 |
Correct |
96 ms |
182252 KB |
Output is correct |
6 |
Correct |
97 ms |
182252 KB |
Output is correct |
7 |
Correct |
98 ms |
182252 KB |
Output is correct |
8 |
Correct |
96 ms |
182292 KB |
Output is correct |
9 |
Correct |
100 ms |
182288 KB |
Output is correct |
10 |
Correct |
98 ms |
182252 KB |
Output is correct |
11 |
Correct |
98 ms |
182380 KB |
Output is correct |
12 |
Correct |
96 ms |
182380 KB |
Output is correct |
13 |
Correct |
99 ms |
182380 KB |
Output is correct |
14 |
Correct |
99 ms |
182380 KB |
Output is correct |
15 |
Correct |
97 ms |
182380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
182252 KB |
Output is correct |
2 |
Correct |
96 ms |
182252 KB |
Output is correct |
3 |
Correct |
97 ms |
182252 KB |
Output is correct |
4 |
Correct |
96 ms |
182380 KB |
Output is correct |
5 |
Correct |
96 ms |
182252 KB |
Output is correct |
6 |
Correct |
97 ms |
182252 KB |
Output is correct |
7 |
Correct |
97 ms |
182380 KB |
Output is correct |
8 |
Correct |
96 ms |
182252 KB |
Output is correct |
9 |
Correct |
96 ms |
182252 KB |
Output is correct |
10 |
Correct |
97 ms |
182252 KB |
Output is correct |
11 |
Correct |
100 ms |
182508 KB |
Output is correct |
12 |
Correct |
98 ms |
182508 KB |
Output is correct |
13 |
Correct |
97 ms |
182380 KB |
Output is correct |
14 |
Correct |
97 ms |
182380 KB |
Output is correct |
15 |
Correct |
98 ms |
182380 KB |
Output is correct |
16 |
Correct |
96 ms |
182252 KB |
Output is correct |
17 |
Correct |
98 ms |
182380 KB |
Output is correct |
18 |
Correct |
100 ms |
182380 KB |
Output is correct |
19 |
Correct |
98 ms |
182380 KB |
Output is correct |
20 |
Correct |
96 ms |
182508 KB |
Output is correct |
21 |
Correct |
99 ms |
182252 KB |
Output is correct |
22 |
Correct |
96 ms |
182252 KB |
Output is correct |
23 |
Incorrect |
100 ms |
182380 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
182380 KB |
Output is correct |
2 |
Correct |
98 ms |
182252 KB |
Output is correct |
3 |
Correct |
97 ms |
182380 KB |
Output is correct |
4 |
Correct |
99 ms |
182252 KB |
Output is correct |
5 |
Correct |
98 ms |
182252 KB |
Output is correct |
6 |
Correct |
95 ms |
182252 KB |
Output is correct |
7 |
Correct |
97 ms |
182252 KB |
Output is correct |
8 |
Correct |
95 ms |
182252 KB |
Output is correct |
9 |
Correct |
96 ms |
182252 KB |
Output is correct |
10 |
Correct |
97 ms |
182252 KB |
Output is correct |
11 |
Correct |
98 ms |
182380 KB |
Output is correct |
12 |
Correct |
98 ms |
182380 KB |
Output is correct |
13 |
Correct |
97 ms |
182380 KB |
Output is correct |
14 |
Correct |
102 ms |
182380 KB |
Output is correct |
15 |
Correct |
103 ms |
182380 KB |
Output is correct |
16 |
Correct |
97 ms |
182380 KB |
Output is correct |
17 |
Correct |
98 ms |
182380 KB |
Output is correct |
18 |
Correct |
97 ms |
182380 KB |
Output is correct |
19 |
Correct |
96 ms |
182380 KB |
Output is correct |
20 |
Correct |
98 ms |
182380 KB |
Output is correct |
21 |
Correct |
96 ms |
182252 KB |
Output is correct |
22 |
Correct |
100 ms |
182400 KB |
Output is correct |
23 |
Incorrect |
98 ms |
182380 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
182312 KB |
Output is correct |
2 |
Correct |
98 ms |
182252 KB |
Output is correct |
3 |
Correct |
102 ms |
182272 KB |
Output is correct |
4 |
Correct |
97 ms |
182252 KB |
Output is correct |
5 |
Correct |
95 ms |
182380 KB |
Output is correct |
6 |
Correct |
96 ms |
182252 KB |
Output is correct |
7 |
Correct |
98 ms |
182380 KB |
Output is correct |
8 |
Correct |
97 ms |
182252 KB |
Output is correct |
9 |
Correct |
97 ms |
182272 KB |
Output is correct |
10 |
Correct |
97 ms |
182252 KB |
Output is correct |
11 |
Correct |
97 ms |
182380 KB |
Output is correct |
12 |
Correct |
96 ms |
182380 KB |
Output is correct |
13 |
Correct |
97 ms |
182380 KB |
Output is correct |
14 |
Correct |
97 ms |
182380 KB |
Output is correct |
15 |
Correct |
98 ms |
182380 KB |
Output is correct |
16 |
Correct |
96 ms |
182252 KB |
Output is correct |
17 |
Correct |
97 ms |
182380 KB |
Output is correct |
18 |
Correct |
96 ms |
182380 KB |
Output is correct |
19 |
Correct |
99 ms |
182252 KB |
Output is correct |
20 |
Correct |
98 ms |
182380 KB |
Output is correct |
21 |
Correct |
97 ms |
182252 KB |
Output is correct |
22 |
Correct |
101 ms |
182252 KB |
Output is correct |
23 |
Incorrect |
101 ms |
182380 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |