#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int MAXN = 30005;
const int SHIFT = 50000;
const int S = 175;
const int INF = 1e9;
int pos[MAXN], p[MAXN];
int n, m;
struct node {
int v, pw, cost;
node () {
}
node (int v_, int pw_, int cost_) {
v = v_;
pw = pw_;
cost = cost_;
}
};
struct Compare_node {
bool operator () (node const &p1, node const &p2) {
return p1.cost < p2.cost;
}
};
vector <int> big[MAXN];
vector <int> small[MAXN];
vector <node> g[MAXN][S];
int dist[MAXN][S];
bool in(int pos) {
return 0 <= pos && pos < n;
}
signed main() {
fastInp;
cin >> n >> m;
set <int> all_small;
for (int i = 0; i < m; i++) {
cin >> pos[i] >> p[i];
if (p[i] >= S) {
big[pos[i]].pb(p[i]);
} else {
small[pos[i]].pb(p[i]);
all_small.insert(p[i]);
}
}
// node -> v pw cost
for (int i = 0; i < n; i++) {
for (int val : all_small) {
if (in(i - val)) {
g[i][val].pb(node(i - val, val, 1));
}
if (in(i + val)) {
g[i][val].pb(node(i + val, val, 1));
}
}
sort(all(small[i]));
small[i].erase(unique(all(small[i])), small[i].end());
for (int val : small[i]) {
g[i][0].pb(node(i, val, 0));
}
}
priority_queue <node, vector<node>, Compare_node> pq;
vector <bool> used(MAXN, false);
memset(dist, -1, sizeof(dist));
pq.push(node(pos[0], 0, 0));
dist[pos[0]][0] = 0;
while (!pq.empty()) {
int v = pq.top().v;
int pw = pq.top().pw;
int cost = -pq.top().cost;
pq.pop();
if (cost > dist[v][pw]) {
continue;
}
if (!used[v]) { // впервые добрались до v
used[v] = 1;
for (int el : big[v]) {
for (int to = v % el; to < n; to += el) {
int c = abs(v - to) / el;
if (dist[to][0] == -1 || dist[to][0] > cost + c) {
dist[to][0] = cost + c;
pq.push(node(to, 0, -dist[to][0]));
}
}
}
}
// change our pw
if (dist[v][0] == -1 || dist[v][0] > dist[v][pw]) {
dist[v][0] = dist[v][pw];
pq.push(node(v, 0, -dist[v][pw]));
}
for (auto el : g[v][pw]) {
int new_v = el.v;
int new_pw = el.pw;
int c = el.cost;
if (dist[new_v][new_pw] == -1 || dist[new_v][new_pw] > dist[v][pw] + c) {
dist[new_v][new_pw] = dist[v][pw] + c;
pq.push(node(new_v, new_pw, -dist[new_v][new_pw]));
}
}
}
cout << dist[pos[1]][0] << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
145540 KB |
Output is correct |
2 |
Correct |
80 ms |
145548 KB |
Output is correct |
3 |
Correct |
81 ms |
145504 KB |
Output is correct |
4 |
Correct |
82 ms |
145476 KB |
Output is correct |
5 |
Correct |
82 ms |
145456 KB |
Output is correct |
6 |
Correct |
80 ms |
145472 KB |
Output is correct |
7 |
Correct |
80 ms |
145540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
145516 KB |
Output is correct |
2 |
Correct |
80 ms |
145552 KB |
Output is correct |
3 |
Correct |
81 ms |
145452 KB |
Output is correct |
4 |
Correct |
85 ms |
145476 KB |
Output is correct |
5 |
Correct |
82 ms |
145460 KB |
Output is correct |
6 |
Correct |
81 ms |
145564 KB |
Output is correct |
7 |
Correct |
81 ms |
145528 KB |
Output is correct |
8 |
Correct |
80 ms |
145476 KB |
Output is correct |
9 |
Correct |
80 ms |
145604 KB |
Output is correct |
10 |
Correct |
90 ms |
145732 KB |
Output is correct |
11 |
Correct |
83 ms |
145816 KB |
Output is correct |
12 |
Correct |
83 ms |
145648 KB |
Output is correct |
13 |
Correct |
83 ms |
145600 KB |
Output is correct |
14 |
Correct |
83 ms |
145812 KB |
Output is correct |
15 |
Correct |
94 ms |
145860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
145476 KB |
Output is correct |
2 |
Correct |
80 ms |
145544 KB |
Output is correct |
3 |
Correct |
82 ms |
145564 KB |
Output is correct |
4 |
Correct |
81 ms |
145476 KB |
Output is correct |
5 |
Correct |
80 ms |
145504 KB |
Output is correct |
6 |
Correct |
80 ms |
145464 KB |
Output is correct |
7 |
Correct |
82 ms |
145496 KB |
Output is correct |
8 |
Correct |
82 ms |
145472 KB |
Output is correct |
9 |
Correct |
81 ms |
145556 KB |
Output is correct |
10 |
Correct |
82 ms |
145824 KB |
Output is correct |
11 |
Correct |
82 ms |
145824 KB |
Output is correct |
12 |
Correct |
82 ms |
145608 KB |
Output is correct |
13 |
Correct |
81 ms |
145604 KB |
Output is correct |
14 |
Correct |
82 ms |
145876 KB |
Output is correct |
15 |
Correct |
83 ms |
145852 KB |
Output is correct |
16 |
Correct |
84 ms |
146396 KB |
Output is correct |
17 |
Correct |
99 ms |
149572 KB |
Output is correct |
18 |
Correct |
97 ms |
149944 KB |
Output is correct |
19 |
Correct |
92 ms |
148032 KB |
Output is correct |
20 |
Correct |
92 ms |
145768 KB |
Output is correct |
21 |
Correct |
86 ms |
146500 KB |
Output is correct |
22 |
Correct |
94 ms |
148548 KB |
Output is correct |
23 |
Correct |
96 ms |
149116 KB |
Output is correct |
24 |
Correct |
109 ms |
152288 KB |
Output is correct |
25 |
Correct |
83 ms |
145720 KB |
Output is correct |
26 |
Correct |
102 ms |
151060 KB |
Output is correct |
27 |
Correct |
90 ms |
148092 KB |
Output is correct |
28 |
Correct |
105 ms |
151048 KB |
Output is correct |
29 |
Correct |
100 ms |
147528 KB |
Output is correct |
30 |
Correct |
86 ms |
146080 KB |
Output is correct |
31 |
Correct |
91 ms |
146664 KB |
Output is correct |
32 |
Correct |
89 ms |
146336 KB |
Output is correct |
33 |
Correct |
128 ms |
149732 KB |
Output is correct |
34 |
Correct |
137 ms |
149700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
145476 KB |
Output is correct |
2 |
Correct |
82 ms |
145564 KB |
Output is correct |
3 |
Correct |
81 ms |
145508 KB |
Output is correct |
4 |
Correct |
82 ms |
145480 KB |
Output is correct |
5 |
Correct |
82 ms |
145452 KB |
Output is correct |
6 |
Correct |
81 ms |
145512 KB |
Output is correct |
7 |
Correct |
81 ms |
145576 KB |
Output is correct |
8 |
Correct |
82 ms |
145500 KB |
Output is correct |
9 |
Correct |
81 ms |
145572 KB |
Output is correct |
10 |
Correct |
83 ms |
145732 KB |
Output is correct |
11 |
Correct |
86 ms |
145836 KB |
Output is correct |
12 |
Correct |
82 ms |
145568 KB |
Output is correct |
13 |
Correct |
81 ms |
145604 KB |
Output is correct |
14 |
Correct |
83 ms |
145868 KB |
Output is correct |
15 |
Correct |
82 ms |
145800 KB |
Output is correct |
16 |
Correct |
83 ms |
146496 KB |
Output is correct |
17 |
Correct |
97 ms |
149632 KB |
Output is correct |
18 |
Correct |
97 ms |
150008 KB |
Output is correct |
19 |
Correct |
103 ms |
148016 KB |
Output is correct |
20 |
Correct |
81 ms |
145784 KB |
Output is correct |
21 |
Correct |
84 ms |
146480 KB |
Output is correct |
22 |
Correct |
90 ms |
148468 KB |
Output is correct |
23 |
Correct |
97 ms |
149072 KB |
Output is correct |
24 |
Correct |
111 ms |
152152 KB |
Output is correct |
25 |
Correct |
84 ms |
145808 KB |
Output is correct |
26 |
Correct |
112 ms |
151104 KB |
Output is correct |
27 |
Correct |
97 ms |
148164 KB |
Output is correct |
28 |
Correct |
107 ms |
151048 KB |
Output is correct |
29 |
Correct |
102 ms |
147540 KB |
Output is correct |
30 |
Correct |
89 ms |
146136 KB |
Output is correct |
31 |
Correct |
91 ms |
146736 KB |
Output is correct |
32 |
Correct |
89 ms |
146360 KB |
Output is correct |
33 |
Correct |
129 ms |
149652 KB |
Output is correct |
34 |
Correct |
128 ms |
149572 KB |
Output is correct |
35 |
Correct |
142 ms |
153964 KB |
Output is correct |
36 |
Correct |
108 ms |
151264 KB |
Output is correct |
37 |
Correct |
162 ms |
156716 KB |
Output is correct |
38 |
Correct |
159 ms |
157052 KB |
Output is correct |
39 |
Correct |
162 ms |
157092 KB |
Output is correct |
40 |
Correct |
180 ms |
157076 KB |
Output is correct |
41 |
Correct |
161 ms |
157076 KB |
Output is correct |
42 |
Correct |
109 ms |
151364 KB |
Output is correct |
43 |
Correct |
97 ms |
148452 KB |
Output is correct |
44 |
Correct |
88 ms |
145984 KB |
Output is correct |
45 |
Correct |
209 ms |
157700 KB |
Output is correct |
46 |
Correct |
209 ms |
157616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
145488 KB |
Output is correct |
2 |
Correct |
81 ms |
145476 KB |
Output is correct |
3 |
Correct |
81 ms |
145460 KB |
Output is correct |
4 |
Correct |
80 ms |
145476 KB |
Output is correct |
5 |
Correct |
79 ms |
145548 KB |
Output is correct |
6 |
Correct |
84 ms |
145456 KB |
Output is correct |
7 |
Correct |
94 ms |
145532 KB |
Output is correct |
8 |
Correct |
81 ms |
145476 KB |
Output is correct |
9 |
Correct |
81 ms |
145532 KB |
Output is correct |
10 |
Correct |
82 ms |
145736 KB |
Output is correct |
11 |
Correct |
82 ms |
145924 KB |
Output is correct |
12 |
Correct |
85 ms |
145604 KB |
Output is correct |
13 |
Correct |
83 ms |
145548 KB |
Output is correct |
14 |
Correct |
83 ms |
145864 KB |
Output is correct |
15 |
Correct |
84 ms |
145860 KB |
Output is correct |
16 |
Correct |
85 ms |
146404 KB |
Output is correct |
17 |
Correct |
110 ms |
149652 KB |
Output is correct |
18 |
Correct |
106 ms |
149976 KB |
Output is correct |
19 |
Correct |
91 ms |
148000 KB |
Output is correct |
20 |
Correct |
81 ms |
145684 KB |
Output is correct |
21 |
Correct |
82 ms |
146536 KB |
Output is correct |
22 |
Correct |
94 ms |
148464 KB |
Output is correct |
23 |
Correct |
96 ms |
149092 KB |
Output is correct |
24 |
Correct |
109 ms |
152080 KB |
Output is correct |
25 |
Correct |
95 ms |
145716 KB |
Output is correct |
26 |
Correct |
119 ms |
151104 KB |
Output is correct |
27 |
Correct |
92 ms |
148056 KB |
Output is correct |
28 |
Correct |
106 ms |
151108 KB |
Output is correct |
29 |
Correct |
101 ms |
147600 KB |
Output is correct |
30 |
Correct |
86 ms |
146040 KB |
Output is correct |
31 |
Correct |
94 ms |
146756 KB |
Output is correct |
32 |
Correct |
90 ms |
146300 KB |
Output is correct |
33 |
Correct |
134 ms |
149572 KB |
Output is correct |
34 |
Correct |
124 ms |
149660 KB |
Output is correct |
35 |
Correct |
136 ms |
153996 KB |
Output is correct |
36 |
Correct |
115 ms |
151324 KB |
Output is correct |
37 |
Correct |
169 ms |
156612 KB |
Output is correct |
38 |
Correct |
158 ms |
157124 KB |
Output is correct |
39 |
Correct |
160 ms |
157148 KB |
Output is correct |
40 |
Correct |
165 ms |
157112 KB |
Output is correct |
41 |
Correct |
189 ms |
157072 KB |
Output is correct |
42 |
Correct |
111 ms |
151364 KB |
Output is correct |
43 |
Correct |
97 ms |
148412 KB |
Output is correct |
44 |
Correct |
87 ms |
146004 KB |
Output is correct |
45 |
Correct |
230 ms |
157612 KB |
Output is correct |
46 |
Correct |
215 ms |
157588 KB |
Output is correct |
47 |
Correct |
554 ms |
213988 KB |
Output is correct |
48 |
Correct |
401 ms |
225424 KB |
Output is correct |
49 |
Correct |
325 ms |
209736 KB |
Output is correct |
50 |
Correct |
333 ms |
204612 KB |
Output is correct |
51 |
Correct |
594 ms |
249260 KB |
Output is correct |
52 |
Runtime error |
512 ms |
262148 KB |
Execution killed with signal 9 |
53 |
Halted |
0 ms |
0 KB |
- |