Submission #61205

#	Time	Username	Problem	Language	Result	Execution time	Memory
61205		Vahan	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1856 ms	103160 KiB

crocodile

#include "crocodile.h"
#include<vector>
#include<set>
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];
set<pair<long long,long long > > ss;
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;
        ar[P[i]]=0;
        ss.insert(mp(0,P[i]));
    }
    for(int i=0;i<N;i++)
    {
        if(ss.empty())
            break;
        int v=ss.begin()->second;
        ss.erase(ss.begin());
        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])
            {
                ss.erase(mp(er[to],to));
                er[to]=ar[to];
                ss.insert(mp(er[to],to));
                ar[to]=dis+d[v];
            }
            else if(er[to]>dis+d[v])
            {
                ss.erase(mp(er[to],to));
                er[to]=d[v]+dis;
                ss.insert(mp(er[to],to));
            }

        }
    }
    return d[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:37: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: 43 / 43
• Subtask 3: 11 / 11