oj.uz

Submission #775803

# Submission time Handle Problem Language Result Execution time Memory
775803 2023-07-07T03:28:02 Z NoLove Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 561 ms 69588 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e18;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    // process input
    vector<pair<int, int>> adj[N];
    for (int 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]});
    }
//    // {T2, T1} (T1 < T2)
    pair<int, int> dp[N + 1]; // dp[i]: minumum time from node i to escape
    memset(dp, 0x3f3f3f, N*sizeof(dp[0]));
    // dijkstra
    set<pair<int, int>> q;
    for (int i = 0; i < K; i++) {
        q.insert({0, P[i]});
        dp[P[i]] = {0, 0};
    }
    while (q.size()) {
        int v = q.begin()->second;
        int c = q.begin()->first;
        q.erase(q.begin());
        if (c != dp[v].first) continue;
        for (auto[u, cost] : adj[v]) {
            if (dp[v].first + cost < dp[u].first) {
                if (dp[v].first + cost < dp[u].second) {
                    dp[u].first = dp[u].second;
                    dp[u].second = dp[v].first + cost;
                } else {
                    dp[u].first = dp[v].first + cost;
                }
                q.insert({dp[u].first, u});
            }
        }
    }
    return dp[0].first;
}

Compilation message

crocodile.cpp:3:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    3 | const int INF = 1e18;
      |                 ^~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:14:41: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   14 |     memset(dp, 0x3f3f3f, N*sizeof(dp[0]));
      |                                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from crocodile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 828 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 828 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 355 ms 59708 KB Output is correct
17 Correct 79 ms 18380 KB Output is correct
18 Correct 113 ms 19196 KB Output is correct
19 Correct 561 ms 69588 KB Output is correct
20 Correct 221 ms 47244 KB Output is correct
21 Correct 37 ms 7332 KB Output is correct
22 Correct 250 ms 45688 KB Output is correct