Submission #938670

#	Time	Username	Problem	Language	Result	Execution time	Memory
938670		Zero_OP	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	357 ms	49176 KiB

crocodile

#include<bits/stdc++.h>

using namespace std;
using int64 = int64_t;

#define     REP(i, n) for(int i = 0, _n = n; i < _n; ++i)
#define    REPD(i, n) for(int i = n - 1; i >= 0; --i)
#define  FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i)
#define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i)
#define          left __left
#define         right __right
#define          prev __prev
#define          next __next
#define           div __div
#define            pb push_back
#define            pf push_front
#define         sz(v) (int)v.size()
#define      range(v) begin(v), end(v)
#define    compact(v) v.erase(unique(range(v)), end(v))
#define      debug(v) "[" #v " = " << (v) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            a = b;
            return true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            a = b;
            return true;
        }
        return false;
    }

template<int dimension, class T>
struct vec : public vector<vec<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {}
};

template<class T>
struct vec<1, T> : public vector<T> {
    vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
    vector<vector<pair<int, int>>> adj(n);
    REP(i, m){
        int u = R[i][0], v = R[i][1], w = L[i];
        adj[u].pb(make_pair(v, w));
        adj[v].pb(make_pair(u, w));
    }

    priority_queue<pair<int64, int>, vector<pair<int64, int>>, greater<pair<int64, int>>> pq;
    vector<int64> best(n, LLONG_MAX), second_best(n, LLONG_MAX);

    REP(i, k){
        best[P[i]] = 0;
        second_best[P[i]] = 0;
        pq.push({0, P[i]});
    }

    vector<bool> mark(n);
    while(!pq.empty()){
        int64 cost;
        int u;
        tie(cost, u) = pq.top(); pq.pop();

        if(mark[u]) continue;
        mark[u] = true;

        for(auto [v, w] : adj[u]){
            if(second_best[u] + w < second_best[v]){
                second_best[v] = second_best[u] + w;
                if(best[v] > second_best[v]) swap(best[v], second_best[v]);
                if(second_best[v] != LLONG_MAX) pq.push(make_pair(second_best[v], v));
            }
        }
    }

    return (int)second_best[0];
}

//#define Zero_OP //turn off when submitting
#ifdef Zero_OP

void init(void);
void process(void);

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) {
        init();
        process();
    }

    return 0;
}

void init(){

}

void process(){
    int R[4][2]; R[0][0] = 0; R[0][1] = 1; R[1][0] = 0; R[1][1] = 2; R[2][0] = 3; R[2][1] = 2; R[3][0] = 2; R[3][1] = 4;
    int L[4]; L[0] = 2; L[1] = 3; L[2] = 1; L[3] = 4;
    int P[3]; P[0] = 1; P[1] = 3; P[2] = 4;
    cout << travel_plan(5, 4, R, L, 3, P);
}

#endif

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:78:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         for(auto [v, w] : adj[u]){
      |                  ^

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