Submission #667076

#	Time	Username	Problem	Language	Result	Execution time	Memory
667076		1bin	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	485 ms	45200 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.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]);
    }
    
    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();
        d = -d;
        if(++v[x] != 2) continue;
        
        for(auto&[nx, p] : adj[x]){
            ll nxd = d + p;
            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];
    int ans;
    cin >> ans;
    cout << travel_plan(n, m, R, L, k, P);
    cout << ' ' << ans << '\n';
    return 0;
}
*/

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11