이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct edge{
int v, c;
};
const int maxpow = 2000;
const int dqsize = 4002005;
int n,m,k,x,y,z;
int pos[4002005], power[4002005];
vector<edge> gph[4002005];
int dis[4002005], inq[4002005];
int nxt[4002005], 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[f(pos[1],power[1])] = 0;
push_back(f(pos[1],power[1]));
inq[f(pos[1],power[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 >> pos[i] >> power[i];
for (int i = 1; i <= m; i++) pos[i]++;
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});
}
for (int i = 1; i <= m; i++) gph[n*maxpow+pos[i]].push_back({f(pos[i],power[i]),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... |