oj.uz

Submission #1111663

# Submission time Handle Problem Language Result Execution time Memory
1111663 2024-11-12T13:50:16 Z michified Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 367 ms 61632 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 < 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 4600 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 4600 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 4 ms 2896 KB Output is correct
13 Correct 5 ms 2896 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 2 ms 508 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 4600 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 4688 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 4 ms 2896 KB Output is correct
13 Correct 5 ms 2896 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 2 ms 508 KB Output is correct
16 Correct 277 ms 56232 KB Output is correct
17 Correct 62 ms 13636 KB Output is correct
18 Correct 95 ms 15228 KB Output is correct
19 Correct 367 ms 61632 KB Output is correct
20 Correct 203 ms 47528 KB Output is correct
21 Correct 46 ms 6048 KB Output is correct
22 Correct 208 ms 45932 KB Output is correct