Submission #200973

#TimeUsernameProblemLanguageResultExecution timeMemory
200973DavidDamianCrocodile's Underground City (IOI11_crocodile)C++11
100 / 100
710 ms50424 KiB
#include "crocodile.h" #include<bits/stdc++.h> using namespace std; struct node { int data; int key; }; node A[1000005]; int heapSize=0; int leftNode(int i) { return i*2; } int rightNode(int i) { return i*2+1; } int parent(int i) { return i/2; } void minHeapify(int i) { int L=leftNode(i); int R=rightNode(i); int best; if(L<=heapSize && A[L].key<A[i].key) best=L; else best=i; if(R<=heapSize && A[R].key<A[best].key) best=R; if(best!=i){ swap(A[i],A[best]); minHeapify(best); } } void decreaseKey(int i,int key) { if(A[i].key<key) return; A[i].key=key; while(i>1 && A[i].key<A[parent(i)].key){ swap(A[i],A[parent(i)]); i=parent(i); } } void heapInsert(node x) { A[++heapSize]=x; A[heapSize].key=1000000007; decreaseKey(heapSize,x.key); } node extractMin() { node minimum=A[1]; A[1]=A[heapSize--]; minHeapify(1); return minimum; } struct edge { int to; int w; }; vector<edge> adjList[100005]; int entrances[100005]; int color[100005]; int d[100005][2]; //0 is primary distance (shortest path), //1 is secondary distance (second shortest path) #define debug(x) cout<<#x<<" = "<<x<<endl #define INF 1000000007 void relax(int u,int v,int w) { if(d[u][1]+w<d[v][0]){ d[v][1]=d[v][0]; d[v][0]=d[u][1]+w; node x={v,d[v][1]}; heapInsert(x); } else if(d[u][1]+w<d[v][1]){ d[v][1]=d[u][1]+w; node x={v,d[v][1]}; heapInsert(x); } } int dijkstra(int n,int k,int p[]) { for(int i=0;i<n;i++){ d[i][0]=d[i][1]=INF; } for(int i=0;i<k;i++){ int u=p[i]; d[u][0]=d[u][1]=0; node x={u,0}; heapInsert(x); } while(heapSize){ node x=extractMin(); int u=x.data; if(color[u]==1) continue; color[u]=1; for(edge e: adjList[u]){ int v=e.to; relax(u,v,e.w); } } return d[0][1]; //Secondary distance of node 0 (second best) } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for(int i=0;i<M;i++){ int u=R[i][0]; int v=R[i][1]; edge e={v,L[i]}; adjList[u].push_back(e); e.to=u; adjList[v].push_back(e); } return dijkstra(N,K,P); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...