Submission #1264742

#TimeUsernameProblemLanguageResultExecution timeMemory
1264742marcus06Crocodile's Underground City (IOI11_crocodile)C++20
100 / 100
285 ms48824 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using lli = long long; #ifdef LOCAL #include </home/marcus06/CP/Library/debug.h> #else #define debug(...) #endif /*How to use: Tvector <int, 2> g(n); //graph Tvector <int, 3> f(n, k, 2) = f[n][k][2] */ template <class Tp, int D = 1> struct Tvector : public vector<Tvector<Tp, D - 1>> { template <class... Args> Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {} }; template <class Tp> struct Tvector<Tp, 1> : public vector<Tp> { Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {} }; const int inf = int(1e9) + 7; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { Tvector <pair <int, int>, 2> graph(N); for (int i = 0; i < M; ++i) { int u = R[i][0], v = R[i][1]; graph[u].emplace_back(v, L[i]); graph[v].emplace_back(u, L[i]); } priority_queue <pair <lli, int>> Q; Tvector <int, 2> dist(N, 2, inf); for (int i = 0; i < K; ++i) { Q.emplace(0, P[i]); dist[P[i]][0] = dist[P[i]][1] = 0; } while (!Q.empty()) { auto [d, u] = Q.top(); Q.pop(); d = -d; if (d > dist[u][1]) continue; for (auto [v, w]: graph[u]) { int nxt_dist = d + w; if (dist[v][0] > nxt_dist) { if (dist[v][0] < dist[v][1]) { dist[v][1] = dist[v][0]; Q.emplace(-dist[v][1], v); } dist[v][0] = nxt_dist; } else if (dist[v][1] > nxt_dist) { dist[v][1] = nxt_dist; Q.emplace(-dist[v][1], v); } } } return dist[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...