Submission #1193746

#TimeUsernameProblemLanguageResultExecution timeMemory
1193746Hamed_GhaffariCrocodile's Underground City (IOI11_crocodile)C++20
100 / 100
282 ms47332 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define X first #define Y second const int MXN = 1e5+5; const int inf = 1e9; vector<pii> g[MXN]; int dis[MXN]; bool mark[MXN]; pii st[MXN]; priority_queue<pii> pq; inline void upd(int v, int d) { dis[v] = d; for(auto [u, w] : g[v]) if(d+w<st[u].Y) { st[u].Y = d+w; if(st[u].Y<st[u].X) swap(st[u].X, st[u].Y); pq.push({-st[u].Y, u}); } } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int i=0; i<M; i++) { g[R[i][0]].push_back({R[i][1], L[i]}); g[R[i][1]].push_back({R[i][0], L[i]}); } fill(st, st+N, pii(inf, inf)); for(int i=0; i<N; i++) upd(i, inf); for(int i=0; i<K; i++) upd(P[i], 0), mark[P[i]] = 1; while(!pq.empty()) { int d = -pq.top().X; int v = pq.top().Y; pq.pop(); if(mark[v]) continue; upd(v, d); mark[v] = 1; } return dis[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...