Submission #200659

#	Time	Username	Problem	Language	Result	Execution time	Memory
200659		DavidDamian	Crocodile's Underground City (IOI11_crocodile)	C++11	0 / 100	6 ms	2680 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
    int to;
    ll w;
};
vector<edge> adjList[100005];
ll first[100005]; //Shortest path to that node from an exit
ll second[100005]; //Second shortest path to that node from an exit
struct node
{
    int data;
    ll key;
};
node A[1000006];
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=1000000000;
    decreaseKey(heapSize,x.key);
}
node extractMin()
{
    node minimum=A[1];
    A[1]=A[heapSize--];
    minHeapify(1);
    return minimum;
}
int degree[100005];
void relax(int u,int v,ll w)
{
    if(degree[v]>2) return;
    if(second[u]+w<first[v]){
        second[v]=first[v];
        first[v]=second[u]+w;
        node x={v,second[v]};
        if(degree[v]==2)
            heapInsert(x);
    }
    else if(second[u]+w<second[v]){
        second[v]=second[u]+w;
        node x={v,second[v]};
        if(degree[v]==2)
            heapInsert(x);
    }
}
int p[100005];
void dijkstra(int n,int k)
{
    for(int i=0;i<n+1;i++){
        first[i]=second[i]=INT_MAX;
    }
    for(int i=0;i<k;i++){
        int u=p[i];
        first[u]=second[u]=0;
        node x={u,0};
        heapInsert(x);
    }
    while(heapSize){
        node u=extractMin();
        for(edge e: adjList[u.data]){
            degree[e.to]++;
            relax(u.data,e.to,e.w);
        }
    }
}
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);
    }
    for(int i=0;i<K;i++){
        p[i]=P[i];
    }
    dijkstra(N,K);
    int secondBest=second[0];
    return secondBest;
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11