oj.uz

Submission #62821

# Submission time Handle Problem Language Result Execution time Memory
62821 2018-07-30T10:28:30 Z Bodo171 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 2000 ms 141448 KB 
#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;
          pq.push({-di,nod});
      }
  }
  return d[0];
}

Compilation message

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 6 ms 2932 KB Output is correct
3 Correct 6 ms 3152 KB Output is correct
4 Correct 5 ms 3200 KB Output is correct
5 Correct 8 ms 3236 KB Output is correct
6 Correct 7 ms 3312 KB Output is correct
7 Correct 6 ms 3388 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 6 ms 2932 KB Output is correct
3 Correct 6 ms 3152 KB Output is correct
4 Correct 5 ms 3200 KB Output is correct
5 Correct 8 ms 3236 KB Output is correct
6 Correct 7 ms 3312 KB Output is correct
7 Correct 6 ms 3388 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 9 ms 4076 KB Output is correct
10 Correct 5 ms 4076 KB Output is correct
11 Correct 6 ms 4076 KB Output is correct
12 Correct 16 ms 4680 KB Output is correct
13 Correct 14 ms 4936 KB Output is correct
14 Correct 6 ms 4936 KB Output is correct
15 Correct 7 ms 4936 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 6 ms 2932 KB Output is correct
3 Correct 6 ms 3152 KB Output is correct
4 Correct 5 ms 3200 KB Output is correct
5 Correct 8 ms 3236 KB Output is correct
6 Correct 7 ms 3312 KB Output is correct
7 Correct 6 ms 3388 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 9 ms 4076 KB Output is correct
10 Correct 5 ms 4076 KB Output is correct
11 Correct 6 ms 4076 KB Output is correct
12 Correct 16 ms 4680 KB Output is correct
13 Correct 14 ms 4936 KB Output is correct
14 Correct 6 ms 4936 KB Output is correct
15 Correct 7 ms 4936 KB Output is correct
16 Correct 1894 ms 114288 KB Output is correct
17 Correct 126 ms 114288 KB Output is correct
18 Correct 186 ms 114288 KB Output is correct
19 Execution timed out 2033 ms 141448 KB Time limit exceeded
20 Halted 0 ms 0 KB -