This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct edge{
int v, c;
};
const int maxpow = 173;
const int dqsize = 5500000;
int n,m,k,x,y,z;
int pos[3], power[3];
vector<edge> gph[5500000];
int dis[5500000];
vector<bool> inq(5500000);
int nxt[5500000], head, tail;
int f(int i, int j) { //2d to 1d
return (i-1)*maxpow+j;
}
bool empty() {
return head == tail;
}
void push_back(int x) {
nxt[tail] = x;
tail = (tail+1) % dqsize;
}
void push_front(int x) {
head = (head-1+dqsize) % dqsize;
nxt[head] = x;
}
int front() {
return nxt[head];
}
int back() {
return nxt[(tail-1+dqsize) % dqsize];
}
void pop_front() {
head = (head+1) % dqsize;
}
void pop_back() {
tail = (tail-1+dqsize) % dqsize;
}
void spfa() {
for (int i = 1; i <= n*maxpow+n; i++) dis[i] = 1e9;
dis[n*maxpow+pos[1]] = 0;
push_back(n*maxpow+pos[1]);
inq[n*maxpow+pos[1]] = 1;
while (!empty()) {
auto tmp = front();
pop_front();
inq[tmp] = 0;
for (auto i : gph[tmp]) {
if (dis[tmp] + i.c < dis[i.v]) {
dis[i.v] = dis[tmp] + i.c;
if (!inq[i.v]) push_back(i.v);
inq[i.v] = 1;
if (dis[back()] < dis[front()]){
push_front(back());
pop_back();
}
}
}
}
if (dis[n*maxpow+pos[2]] == 1e9) cout << "-1\n";
else cout << dis[n*maxpow+pos[2]] << '\n';
}
int main() {
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
x++;
if (y > maxpow) {
for (int j = x - y, c = 1; j >= 1; j -= y, c++)
gph[n*maxpow+x].push_back({n*maxpow+j,c});
for (int j = x + y, c = 1; j <= n; j += y, c++)
gph[n*maxpow+x].push_back({n*maxpow+j,c});
} else {
gph[n*maxpow+x].push_back({f(x,y),0});
}
if (i <= 2) pos[i] = x, power[i] = y;
}
for (int i = 1; i <= maxpow; i++) { //pow
for (int j = 1; j <= i; j++) {
for (int l = j; l+i <= n; l += i) { //pos
gph[f(l,i)].push_back({f(l+i,i),1});
gph[f(l+i,i)].push_back({f(l,i),1});
}
}
for (int j = 1; j <= n; j++) gph[f(j,i)].push_back({n*maxpow+j,0});
}
spfa();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |