이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
#define compress(v) v.erase(unique(all(v)),v.end())
using namespace std;
const int INF = (int)1e9;
struct edge {
int v, cost;
bool operator<(const edge& tmp)const {
return cost > tmp.cost;
}
};
int N,M;
int B[30000];
vector<int> P[30000];
map<int, bool> Used[30000];
vector<edge> Edge[30000];
int Dist[30000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < M; i++) {
int p;
cin >> B[i] >> p;
P[B[i]].push_back(p);
}
for (int i = 0; i < N; i++) {
for (int j : P[i]) {
for (int k = 1; i - k * j >= 0; k++) {
Edge[i].push_back({ i - k * j,k });
if (Used[i - k * j][j])
break;
Used[i - k * j][j] = true;
}
}
}
for (int i = N - 1; i >= 0; i--) {
Used[i].clear();
for (int j : P[i]) {
for (int k = 1; i + k * j < N; k++) {
Edge[i].push_back({ i + k * j,k });
if (Used[i + k * j][j])
break;
Used[i + k * j][j] = true;
}
}
}
priority_queue<edge> q;
fill(Dist, Dist + N, INF);
Dist[B[0]] = 0;
q.push({ B[0],0});
while (!q.empty()) {
auto t = q.top();
q.pop();
if (Dist[t.v] < t.cost)
continue;
for (edge i : Edge[t.v]) {
if (Dist[i.v] > t.cost + i.cost) {
Dist[i.v] = t.cost + i.cost;
q.push({ i.v,Dist[i.v] });
}
}
}
int ans = Dist[B[1]];
if (ans == INF)
ans = -1;
cout << ans;
return 0;
}
# | 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... |