oj.uz

Submission #899747

# Submission time Handle Problem Language Result Execution time Memory
899747 2024-01-06T23:50:40 Z lalig777 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 446 ms 94148 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include "crocodile.h"
using namespace std;
 
typedef long long ll;
const ll INF=1e18+1;
 
int travel_plan(int N, int M, int R[][2], int S[], int K, int P[]){
  vector<vector<pair<int,ll> > > listaAdy(N);
  for (int i=0; i<M; i++){
    listaAdy[R[i][0]].push_back(make_pair(R[i][1], S[i]));
    listaAdy[R[i][1]].push_back(make_pair(R[i][0], S[i]));
  }
  vector<pair<ll,ll> > dist(N, make_pair(INF, INF));
  priority_queue<pair<ll, int> >pq;
  for (int i=0; i<K; i++){
    dist[P[i]].first=0;
    dist[P[i]].second=0;
    pq.push(make_pair(0, P[i]));
  }
  while (!pq.empty()){
    int u=pq.top().second;
    ll d=-pq.top().first;
    pq.pop();
    if (dist[u].second<d) continue;
    if (dist[u].first<=d) dist[u].second=d;
    else{
      dist[u].second=dist[u].first;
      dist[u].first=d;
    }
    if (dist[u].second==INF) continue;
    for (auto vec: listaAdy[u]){
      int v=vec.first;
      ll c=vec.second;
      ll dact=dist[u].second+c;
      if(dist[v].second>dact){
        dist[v].second=dact;
        if (dist[v].second<dist[v].first){
          dist[v].second=dist[v].first;
          dist[v].first=dact;
        }pq.push(make_pair(-dist[v].second, v));
      }
    }
  }
  if (dist[0].second==INF) return -1;
  return dist[0].second;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 4952 KB Output is correct
13 Correct 3 ms 5068 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4800 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 4952 KB Output is correct
13 Correct 3 ms 5068 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4800 KB Output is correct
16 Correct 319 ms 81820 KB Output is correct
17 Correct 78 ms 21632 KB Output is correct
18 Correct 89 ms 23944 KB Output is correct
19 Correct 446 ms 94148 KB Output is correct
20 Correct 217 ms 66384 KB Output is correct
21 Correct 33 ms 11724 KB Output is correct
22 Incorrect 245 ms 64796 KB Output isn't correct
23 Halted 0 ms 0 KB -