Submission #1264529

#TimeUsernameProblemLanguageResultExecution timeMemory
1264529marcus06Crocodile's Underground City (IOI11_crocodile)C++20
0 / 100
0 ms320 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) {} }; 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; vector <bool> vis(N); vector <lli> dist(N, -1); dist[0] = 0; Q.emplace(0, 0); while (!Q.empty()) { auto [d, u] = Q.top(); Q.pop(); if (vis[u]) continue; vis[u] = true; for (auto [v, w]: graph[u]) { if (dist[v] == -1 || dist[v] > dist[u] + w) { dist[v] = dist[u] + w; Q.emplace(-dist[v], v); } } } lli ans = 0; for (int i = 0; i < K; ++i) { ans = max(ans, dist[P[i]]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...