oj.uz

Submission #123624

# Submission time Handle Problem Language Result Execution time Memory
123624 2019-07-01T19:18:33 Z deinfreund Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1053 ms 71908 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
 
vector<vector<int>> conns;
vector<vector<int>> costs;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  conns.resize(N);
  costs.resize(N);
  for (int i = 0; i < M; i++){
    int a = R[i][0];
    int b = R[i][1];
    conns[a].push_back(b);
    conns[b].push_back(a);
    costs[a].push_back(L[i]);
    costs[b].push_back(L[i]);
  }
  const long long big = 1000000000;//100000000000000000LL;
  vector<long long> firstCost(N, big);
  vector<long long> secondCost(N, big);
  priority_queue<pair<long long, int>> pq;
  for (int i = 0; i < K; i++){
    pq.push({0, P[i]});
  }
  vector<bool> visited(N, 0);
  while (!pq.empty()){
    int pos;
    long long cost;
    do{
      pos = pq.top().second;
      cost = -pq.top().first;
      pq.pop();
    }while(visited[pos] && !pq.empty());
    if (visited[pos]) break;
    visited[pos] = 1;
    for (unsigned int i = 0; i < conns[pos].size(); i++){
      if (!visited[conns[pos][i]]){
	long long c = cost + costs[pos][i];
	if (c < secondCost[conns[pos][i]]){
	  if (c < firstCost[conns[pos][i]]){
	    secondCost[conns[pos][i]] = firstCost[conns[pos][i]];
	    firstCost[conns[pos][i]] = c;
	  }else{
	    secondCost[conns[pos][i]] = c;
	  }
	  pq.push({-secondCost[conns[pos][i]], conns[pos][i]});
	}
      }
    }
  }
  return secondCost[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 6 ms 888 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 6 ms 888 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 680 ms 60192 KB Output is correct
17 Correct 149 ms 20716 KB Output is correct
18 Correct 173 ms 22436 KB Output is correct
19 Correct 1053 ms 71908 KB Output is correct
20 Correct 341 ms 48256 KB Output is correct
21 Correct 62 ms 8180 KB Output is correct
22 Correct 419 ms 46552 KB Output is correct