Submission #62822

#	Time	Username	Problem	Language	Result	Execution time	Memory
62822		Bodo171	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1586 ms	85256 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <climits>
#include <iostream>
using namespace std;
const int nmax=100005;
vector< pair<int,long long> > v[nmax];
long long d[nmax];
priority_queue< pair<long long,int> > pq;
int i,s,nod,E[nmax];
long long cost,di;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(i=0;i<M;i++)
  {
     v[R[i][0]].push_back({R[i][1],L[i]});
     v[R[i][1]].push_back({R[i][0],L[i]});
  }
  for(i=0;i<N;i++)
    d[i]=LLONG_MAX;
  for(i=0;i<K;i++)
  {
      d[P[i]]=0;
      pq.push({-d[P[i]],P[i]});
      E[P[i]]=1;
  }
  while(!pq.empty())
  {
      cost=-pq.top().first;
      s=pq.top().second;pq.pop();
      E[s]++;
      if(E[s]!=2) continue;
      d[s]=cost;
      for(i=0;i<v[s].size();i++)
      {
          nod=v[s][i].first;di=d[s]+v[s][i].second;
          if(E[nod]<2)
            pq.push({-di,nod});
      }
  }
  return d[0];
}

Compilation message (stderr)

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

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