이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define forin(i, a, b) for(int i = a; i <= b; ++i)
#define ii pair<int, int>
#define iii pair<int, ii>
using namespace std;
const int N = 3e4 + 10, T = 180;
int n, m, inf;
int b[N], p[N], d[T + 10][N];
vector<int> walk[N];
vector<ii> tele[N];
priority_queue<iii, vector<iii>, greater<iii> > pq;
int main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("Task.inp","r")) {
freopen("Task.inp","r",stdin);
freopen("WA.out","w",stdout);
}
cin>>n>>m;
int s = sqrt(n);
forin(i, 1, m) {
cin>>b[i]>>p[i];
if(p[i] > s) {
int pos = b[i], d = 0;
do {
if(d) tele[b[i]].push_back({pos, d});
pos += p[i];
d++;
} while(pos < n);
pos = b[i]; d = 0;
do {
if(d) tele[b[i]].push_back({pos, d});
pos -= p[i];
d++;
} while(pos >= 0);
}
else walk[b[i]].push_back(p[i]);
}
memset(d, 60, sizeof(d));
inf = d[0][0];
d[0][b[1]] = 0;
pq.push({0, {b[1], 0}});
while(!pq.empty()) {
int kc = pq.top().first;
int u, l; tie(u, l) = pq.top().second;
pq.pop();
if(d[l][u] != kc) continue;
if(l) walk[u].push_back(l);
for(auto e : tele[u]) {
int v, w; tie(v, w) = e;
if(d[0][v] <= kc + w) continue;
d[0][v] = kc + w;
pq.push({d[0][v], {v, 0}});
}
for(auto w : walk[u]) {
if(u - w >= 0) {
if(d[w][u - w] <= kc + 1) continue;
d[w][u - w] = kc + 1;
pq.push({d[w][u - w], {u - w, w}});
}
}
for(auto w : walk[u]) {
if(u + w < n) {
if(d[w][u + w] <= kc + 1) continue;
d[w][u + w] = kc + 1;
pq.push({d[w][u + w], {u + w, w}});
}
}
if(l) walk[u].pop_back();
}
int ans = inf;
forin(i, 0, T) ans = min(ans, d[i][b[2]]);
if(ans == inf) cout<<-1;
else cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |