oj.uz

Submission #200967

# Submission time Handle Problem Language Result Execution time Memory
200967 2020-02-08T21:38:16 Z DavidDamian Crocodile's Underground City (IOI11_crocodile) C++11
46 / 100
 8 ms 3064 KB 
#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];
int color[100005];
ll 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 1000000000007
void relax(int u,int v,ll w)
{
    entrances[v]++;
    if((ll)(d[u][1]+w)<=d[v][0]){
        d[v][1]=d[v][0];
        d[v][0]=d[u][1]+w;
    }
    else if((ll)(d[u][1]+w)<d[v][1]){
        d[v][1]=d[u][1]+w;
    }
    if(entrances[v]==adjList[v].size()-1){
        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);
        }
    }
    d[0][0]=d[0][1]=INF;
    for(edge e: adjList[0]){
        int v=e.to;
        //debug(d[v][1]+e.w);
        if(d[v][1]+e.w<d[0][0]){
            d[0][1]=d[0][0];
            d[0][0]=d[v][1]+e.w;
        }
        else if(d[v][1]+e.w<d[0][1]){
            d[0][1]=d[v][1]+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,(ll)L[i]};
        adjList[u].push_back(e);
        e.to=u;
        adjList[v].push_back(e);
    }
    return dijkstra(N,K,P);
}

Compilation message

crocodile.cpp: In function 'void relax(int, int, ll)':
crocodile.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(entrances[v]==adjList[v].size()-1){
        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 7 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 7 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 8 ms 3064 KB Output is correct
10 Incorrect 6 ms 2808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 7 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 8 ms 3064 KB Output is correct
10 Incorrect 6 ms 2808 KB Output isn't correct
11 Halted 0 ms 0 KB -