oj.uz

Submission #29186

# Submission time Handle Problem Language Result Execution time Memory
29186 2017-07-18T15:17:12 Z kavun Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 896 ms 173196 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
priority_queue <ii> Q;
vector<ii> adj[150010];
int mk[150010];


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

  for(int i = 0; i < M; i++)
    {
      int v = R[i][0], u = R[i][1], l = L[i];
      adj[v].push_back(make_pair(u,l));
      adj[u].push_back(make_pair(v,l));
    }

  for(int i = 0; i < K; i++)
    {
      Q.push(make_pair(0,P[i]));
      mk[P[i]] = 1;
    }

  while(!Q.empty())
    {
      int v = Q.top().second;
      int val = -Q.top().first;
      Q.pop();
      if(mk[v] == 1)
	{
	  for(int i = 0; i < adj[v].size(); i++)
	    Q.push(ii(-(adj[v][i].second + val),adj[v][i].first));
	  if(v == 0)
	    return val;
	}
      mk[v]++;
    }
  return -1;
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 123504 KB Output is correct
2 Correct 0 ms 123504 KB Output is correct
3 Correct 3 ms 123504 KB Output is correct
4 Correct 0 ms 123636 KB Output is correct
5 Correct 0 ms 123640 KB Output is correct
6 Correct 0 ms 123504 KB Output is correct
7 Correct 0 ms 123636 KB Output is correct
8 Correct 0 ms 123504 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 123780 KB Output is correct
2 Correct 0 ms 123504 KB Output is correct
3 Correct 3 ms 123636 KB Output is correct
4 Correct 9 ms 124192 KB Output is correct
5 Correct 3 ms 124272 KB Output is correct
6 Correct 3 ms 123504 KB Output is correct
7 Correct 0 ms 123636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 173196 KB Output is correct
2 Correct 96 ms 128256 KB Output is correct
3 Correct 143 ms 129444 KB Output is correct
4 Correct 896 ms 163268 KB Output is correct
5 Correct 489 ms 171056 KB Output is correct
6 Correct 66 ms 125880 KB Output is correct
7 Correct 733 ms 142640 KB Output is correct