Submission #1005297

#TimeUsernameProblemLanguageResultExecution timeMemory
1005297GrayCrocodile's Underground City (IOI11_crocodile)C++17
100 / 100
491 ms96324 KiB
#include "crocodile.h" #include <queue> #include <utility> #include <vector> #define ll long long #define ff first #define ss second #define ln "\n" using namespace std; const ll INF = 2e18; vector<pair<ll, pair<ll, ll>>> e; vector<vector<ll>> A; ll n, m, k; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { n=N; m=M; k=K; e.resize(m); A.resize(n); for (ll i=0; i<m; i++){ e[i] = {L[i], {R[i][0], R[i][1]}}; A[R[i][0]].push_back(i); A[R[i][1]].push_back(i); } vector<ll> dist(n, INF); vector<ll> vis(n, 0); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll,ll>>> que; for (ll i=0; i<K; i++){ vis[P[i]]=1; que.push({0, P[i]}); } while (!que.empty()){ auto cur = que.top(); que.pop(); if (vis[cur.ss]==2) continue; vis[cur.ss]++; if (vis[cur.ss]==1) {continue;} else dist[cur.ss]=cur.ff; for(auto i:A[cur.ss]){ ll v = e[i].ss.ff^e[i].ss.ss^cur.ss; if (vis[v]<2){ que.push({e[i].ff+cur.ff, v}); } } } return dist[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...