Submission #13529

#TimeUsernameProblemLanguageResultExecution timeMemory
13529aintaCrocodile's Underground City (IOI11_crocodile)C++98
100 / 100
656 ms215336 KiB
#include "crocodile.h" #include<algorithm> #include<vector> using namespace std; vector<int>E[100100], Len[101000]; bool chk[101000]; struct HP{ int d, num; bool operator<(const HP &p)const{ return d>p.d; } }Heap[8000100]; int D[100100][2], top; void Add(int a, int b){ if (D[a][1] <= b)return; if (D[a][0] > b){ D[a][1] = D[a][0]; D[a][0] = b; } else if (D[a][1] > b)D[a][1] = b; Heap[top].d = b; Heap[top].num = a; top++; push_heap(Heap, Heap + top); } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { int i, x; HP t; for (i = 0; i < M; i++){ E[R[i][0]].push_back(R[i][1]); E[R[i][1]].push_back(R[i][0]); Len[R[i][0]].push_back(L[i]); Len[R[i][1]].push_back(L[i]); } for (i = 0; i < N; i++)D[i][0] = D[i][1] = 2100000000; top = 0; for (i = 0; i < K; i++){ D[P[i]][0] = 0; Add(P[i], 0); } while (1){ while (top){ t = Heap[0]; if (D[t.num][1] == t.d && !chk[t.num])break; pop_heap(Heap, Heap + top); top--; } chk[t.num] = true; if (t.num == 0)break; pop_heap(Heap, Heap + top); top--; for (i = 0; i < E[t.num].size(); i++){ Add(E[t.num][i], t.d + Len[t.num][i]); } } return D[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...