oj.uz

Submission #241040

# Submission time Handle Problem Language Result Execution time Memory
241040 2020-06-22T09:54:06 Z lakshith_ Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 405 ms 24516 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define pb push_back

using namespace std;

vector<vector<pair<int,int>>> adjList(1001,vector<pair<int,int>>());

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
  for(int i=0;i<m;i++){
    adjList.at(r[i][0]).pb({r[i][1],l[i]});
    adjList.at(r[i][1]).pb({r[i][0],l[i]});
  }
  //dijsktra
  priority_queue< pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
  vector<pair<int,int>> dist(n);
  for(int i=0;i<n;i++)
    dist.at(i) = {INT_MAX,INT_MAX};
  for(int i=0;i<k;i++){
    pq.push({0,p[i]});
    dist.at(p[i]) = {0,0};
  }
  
  while(!pq.empty()){
    int cost = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if(cost > dist[node].second)continue;
    for(pair<int,int> v : adjList.at(node)){
      int to = v.first;
      int nCost = cost + v.second;
      int prv = dist[to].second;
      if(nCost<dist[to].first)
        dist[to].second = dist[to].first,dist[to].first=nCost;
      else if(nCost<dist[to].second)
        dist[to].second = nCost;
      if(dist[to].second<prv)
        pq.push({dist[to].second,to});
    }
  }
  return dist[0].second;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Runtime error 405 ms 24516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -