Submission #200959

#TimeUsernameProblemLanguageResultExecution timeMemory
200959DavidDamianCrocodile's Underground City (IOI11_crocodile)C++11
0 / 100
6 ms2680 KiB
#include "crocodile.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { int data; ll key; }; node A[100005]; 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[i].key) best=R; if(best!=i){ swap(A[i],A[best]); minHeapify(best); } } void decreaseKey(int i,ll 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=LLONG_MAX; decreaseKey(heapSize,x.key); } node extractMin() { node minimum=A[1]; A[1]=A[heapSize--]; minHeapify(1); return minimum; } struct edge { int to; ll w; }; vector<edge> adjList[100005]; int entrances[100005]; ll d[100005][2]; //0 is primary distance (shortest path), //1 is secondary distance (second shortest path) void relax(int u,int v,ll w) { entrances[v]++; if(d[u][1]+w<d[v][0]){ d[v][1]=d[v][0]; d[v][0]=d[u][1]+w; if(entrances[v]==adjList[v].size()-1 && v!=0){ node x={v,d[v][1]}; heapInsert(x); } } else if(d[u][1]+w<d[v][1]){ d[v][1]=d[u][1]+w; if(entrances[v]==adjList[v].size()-1 && v!=0){ 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]=LLONG_MAX/2; } 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; 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); }

Compilation message (stderr)

crocodile.cpp: In function 'void relax(int, int, ll)':
crocodile.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(entrances[v]==adjList[v].size()-1 && v!=0){
            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(entrances[v]==adjList[v].size()-1 && v!=0){
            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...