Submission #1111663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111663		michified	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	367 ms	61632 KiB

crocodile

#include <bits/stdc++.h>
#define ll long long
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
// #define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

struct edge_t {
    int to, w;
};

struct elem_t {
    int at, c;
};

int travel_plan(int n, int m, int R[][2], int L[], int k, int p[]) {
    vector<vector<edge_t>> adj(n);
    int i, inf = 2e9;
    for (i = 0; i < m; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    auto cmp = [](const auto& a, const auto& b){return a.c > b.c;};
    priority_queue<elem_t, vector<elem_t>, decltype(cmp)> pq(cmp);
    vector<int> best(n, inf), sbest(n, inf);
    for (i = 0; i < k; i++) {
        pq.push({p[i], 0});
        best[p[i]] = 0;
        sbest[p[i]] = 0;
    }
    elem_t cur;
    int cost;
    while (not pq.empty()) {
        cur = pq.top();
        pq.pop();
        if (cur.c != sbest[cur.at]) continue;
        for (auto& e : adj[cur.at]) {
            int cost = cur.c + e.w;
            if (cost < best[e.to]) {
                if (sbest[e.to] != best[e.to]) pq.push({e.to, best[e.to]});
                sbest[e.to] = best[e.to];
                best[e.to] = cost;
            } else if (cost < sbest[e.to]) {
                sbest[e.to] = cost;
                pq.push({e.to, cost});
            }
        }
    }
    return sbest[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:9: warning: unused variable 'cost' [-Wunused-variable]
   42 |     int cost;
      |         ^~~~

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