Submission #667072

#	Time	Username	Problem	Language	Result	Execution time	Memory
667072		1bin	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	3412 KiB

crocodile

#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;
}
*/

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         auto[d, x] = pq.top(); pq.pop();
      |             ^
crocodile.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         for(auto&[nx, p] : adj[x]){
      |                  ^

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