Submission #61198

#	Time	Username	Problem	Language	Result	Execution time	Memory
61198		Vahan	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	12 ms	5456 KiB

crocodile

#include "crocodile.h"
#include<vector>
using namespace std;
#define mp make_pair
const long long MAX=100000000000000000;
long long d[200000],er[200000],ar[200000];
vector<pair<int,int> > g[200000];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0;i<M;i++)
    {
        g[R[i][0]].push_back(mp(R[i][1],L[i]));
        g[R[i][1]].push_back(mp(R[i][0],L[i]));
    }
    for(int i=0;i<N;i++)
    {
        ar[i]=MAX;
        er[i]=MAX;
        d[i]=MAX;
    }
    for(int i=0;i<K;i++)
        er[P[i]]=0;
    for(int i=0;i<N;i++)
    {
        int v=-1;
        for(int j=0;j<N;j++)
            if(d[j]==MAX && (v==-1 || er[j]<er[v]))
                v=j;
        if(v==-1)
            break;
        d[v]=er[v];
        er[v]=MAX;
        for(int j=0;j<g[v].size();j++)
        {
            int to=g[v][j].first;
            int dis=g[v][j].second;
            if(d[to]!=MAX)
                continue;
            if(ar[to]>=dis+d[v])
            {
                er[to]=ar[to];
                ar[to]=dis+d[v];
            }
            else if(er[to]>dis+d[v])
                er[to]=d[v]+dis;
        }
    }
    return d[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[v].size();j++)
                     ~^~~~~~~~~~~~

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