oj.uz

답안 #667073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667073 2022-11-30T10:37:13 Z 1bin 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 6 ms 6740 KB 
#include <bits/stdc++.h>
#include <cassert>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, m, k, dist[NMAX][2], R[NMAX * 10][2], L[NMAX * 10], P[NMAX], v[NMAX], a, b;
vector<pair<int, int>> adj[NMAX];

int travel_plan(int N_, int M_, int R_[][2], int L[], int K_, int P_[]){
    n = N_; m = M_; k = K_;
    for(int i = 0; i < m; i++){
        a = R[i][0]; b = R[i][1];
        adj[a].emplace_back(b, L[i]);
        adj[b].emplace_back(a, L[i]);
        //cout << a << ' ' << b << ' ' << L[i] << '\n';
    }
    
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pair<int, int>> pq;
    for(int i = 0; i < k; i++) {
        dist[P_[i]][0] = dist[P_[i]][1] = 0;
        pq.emplace(0, P_[i]);
        v[P_[i]] = 1;
    }
    
    while(pq.size()){
        auto[d, x] = pq.top(); pq.pop();
        //cout << x << ' ' << d << '\n';
        d = -d;
        if(++v[x] != 2) continue;
        
        for(auto&[nx, p] : adj[x]){
            ll nxd = d + p;
            //cout << "nxd is " << nx << ' ' << nxd << '\n';
            if(nxd < dist[nx][1]){
                pq.emplace(-nxd, nx);
                dist[nx][1] = nxd;
                if(dist[nx][0] > dist[nx][1]) swap(dist[nx][0], dist[nx][1]);
            }
        }
    }
    assert(dist[0][1] <= 1e9);
    return dist[0][1];
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++) cin >> R[i][0] >> R[i][1] >> L[i];
    for(int i = 0; i < k; i++) cin >> P[i];
    cout << travel_plan(n, m, R, L, k, P);
    return 0;
}
*/

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 6740 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 6740 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 6740 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -