이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const int B = 200;
vector<ll> dijkstra(int n, int s, vector<vector<pair<int, int>>> &adj){
vector<ll> dist(n+1, INF);
dist[s] = 0;
vector<bool> vis(n+1, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, s});
while(!pq.empty()){
ll d_u = pq.top().first;
int u = pq.top().second;
pq.pop();
if(vis[u]){
continue;
}
vis[u] = true;
for(auto it : adj[u]){
int v = it.first;
ll w = it.second;
if(vis[v]) continue;
dist[v] = min(dist[v], d_u+w);
pq.push({dist[v], v});
}
}
return dist;
}
void solve(){
int n, m;
cin >> n >> m;
vector<ll> b(m+1), p(m+1);
for(int i = 1; i <= m; i++){
cin >> b[i] >> p[i];
b[i]++;
}
int c = 0;
vector<vector<int>> cv(n+1, vector<int>(B+1));
vector<vector<bool>> have_doge(n+1, vector<bool>(B+1, false));
for(int i = 1; i <= m; i++){
if(p[i] <= B){
have_doge[b[i]][p[i]] = true;
}
}
vector<pair<int, int>> dc;
dc.push_back({-1, -1});
for(int i = 1; i <= n; i++){
for(int j = 0; j <= B; j++){
c++;
cv[i][j] = c;
dc.push_back({i, j});
}
}
int nb = c;
auto valid = [&](int x) -> bool{
return (x >= 1 && x <= n);
};
vector<vector<pair<ll, ll>>> adj(nb+1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= B; j++){
int u, v;
u = cv[i][0];
v = cv[i][j];
if(have_doge[i][j]){
adj[u].push_back({v, 0});
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= B; j++){
int u, v;
if(valid(i+j)){
u = cv[i][j];
v = cv[i+j][0];
adj[u].push_back({v, 1});
v = cv[i+j][j];
adj[u].push_back({v, 1});
}
if(valid(i-j)){
u = cv[i][j];
v = cv[i-j][0];
adj[u].push_back({v, 1});
v = cv[i-j][j];
adj[u].push_back({v, 1});
}
}
}
for(int i = 1; i <= m; i++){
int pos, u, v;
pos = b[i];
if(p[i] <= B) continue;
for(int j = -B; j <= B; j++){
if(valid(pos+j*p[i]) && j != 0){
u = cv[pos][0];
v = cv[pos+j*p[i]][0];
adj[u].push_back({v, abs(j)});
}
}
}
for(int j = 1; j <= n; j++){
if(abs(b[1]-j)%p[1] == 0){
ll w = abs(b[1]-j)/p[1];
adj[0].push_back({cv[j][0], w});
}
}
int S = 0, T = cv[b[2]][0];
vector<ll> dist = dijkstra(nb, S, adj);
ll ans = dist[T];
if(ans == INF){
ans = -1;
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
skyscraper.cpp:5:36: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
5 | const ll maxn = 2*1e5+5, INF = 4e18+9;
| ~~~~^~
# | 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... |