Submission #775803

#	Time	Username	Problem	Language	Result	Execution time	Memory
775803		NoLove	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	561 ms	69588 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11