oj.uz

Submission #1048665

# Submission time Handle Problem Language Result Execution time Memory
1048665 2024-08-08T08:59:45 Z MarwenElarbi Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 298 ms 77636 KB 
#include <bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define pb push_back
#define fi first
#define se second
const int nax=1e5+5;
vector<pair<int,int>> adj[nax];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for (int i = 0; i < M; ++i)
  {
    adj[R[i][0]].pb({R[i][1],L[i]});
    adj[R[i][1]].pb({R[i][0],L[i]});
  }
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
  int vis[N];
  memset(vis,0,sizeof vis);
  for (int i = 0; i < K; ++i)
  {
    pq.push({0,P[i]});
    vis[P[i]]++;
  }
  while(!pq.empty()){
    pair<int,int> node=pq.top();
    pq.pop();
    if(vis[node.se]++ == 1){
      if(node.se==0) return node.fi;
      for(auto u:adj[node.se]){
        pq.push({u.se+node.fi,u.fi});
      }
    }
  }
  return N;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6784 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6916 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6804 KB Output is correct
12 Correct 3 ms 7396 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6788 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6784 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6916 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6804 KB Output is correct
12 Correct 3 ms 7396 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6788 KB Output is correct
16 Correct 227 ms 77636 KB Output is correct
17 Correct 42 ms 14940 KB Output is correct
18 Correct 44 ms 18520 KB Output is correct
19 Correct 244 ms 73288 KB Output is correct
20 Correct 134 ms 54232 KB Output is correct
21 Correct 24 ms 10588 KB Output is correct
22 Correct 298 ms 48080 KB Output is correct