oj.uz

Submission #1111653

# Submission time Handle Problem Language Result Execution time Memory
1111653 2024-11-12T13:19:25 Z michified Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 4544 KB 
#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 < n; 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]) {
                sbest[e.to] = best[e.to];
                best[e.to] = cost;
                pq.push({e.to, cost});
            } else if (cost < sbest[e.to]) {
                sbest[e.to] = cost;
                pq.push({e.to, cost});
            }
        }
    }
    return sbest[0];
}

Compilation message

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
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Incorrect 2 ms 4432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Incorrect 2 ms 4432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Incorrect 2 ms 4432 KB Output isn't correct
5 Halted 0 ms 0 KB -