oj.uz

Submission #241041

# Submission time Handle Problem Language Result Execution time Memory
241041 2020-06-22T09:55:57 Z lakshith_ Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 695 ms 61424 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define pb push_back
 
using namespace std;
 
vector<vector<pair<int,int>>> adjList(100000,vector<pair<int,int>>());
vector<pair<int,int>> dist(100000); 

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;
  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 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3456 KB Output is correct
7 Correct 8 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3456 KB Output is correct
7 Correct 8 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 9 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 10 ms 3840 KB Output is correct
13 Correct 9 ms 3840 KB Output is correct
14 Correct 7 ms 3456 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3456 KB Output is correct
7 Correct 8 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 9 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 10 ms 3840 KB Output is correct
13 Correct 9 ms 3840 KB Output is correct
14 Correct 7 ms 3456 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct
16 Correct 532 ms 41476 KB Output is correct
17 Correct 98 ms 13816 KB Output is correct
18 Correct 124 ms 15352 KB Output is correct
19 Correct 695 ms 61424 KB Output is correct
20 Correct 351 ms 50424 KB Output is correct
21 Correct 48 ms 8312 KB Output is correct
22 Correct 371 ms 46548 KB Output is correct