oj.uz

답안 #1016395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016395 2024-07-08T03:59:50 Z Icelast Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 2 ms 2652 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+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<short>> cv(n+1, vector<short>(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;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= B; j++){
            c++;
            cv[i][j] = c;
        }
    }
    int nb = c;
    auto valid = [&](int x) -> bool{
        return (x >= 1 && x <= n);
    };
    vector<vector<pair<int, int>>> 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();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 2 ms 1368 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Runtime error 2 ms 2588 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Runtime error 2 ms 2652 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1172 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1368 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Runtime error 2 ms 2652 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -