oj.uz

Submission #1105313

# Submission time Handle Problem Language Result Execution time Memory
1105313 2024-10-26T06:29:29 Z Zone_zonee Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 766 ms 106660 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define MAX_N 100000
#define MAX_M 10000000

vector<pair<int, long long>> adj[MAX_N];
long long dis[MAX_N];
int vis[MAX_N];
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]].emplace_back(R[i][1], L[i]);
    adj[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  for(int i = 0; i < K; ++i){
    vis[P[i]] = 1;
    pq.emplace(0LL, P[i]);
  }
  while(!pq.empty()){
    auto [d, u] = pq.top(); pq.pop();
    vis[u]++;
    if(vis[u] == 2){
      dis[u] = d;
      for(auto [v, w] : adj[u]) pq.emplace(d + w, v);
    }
  }
  return dis[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 3 ms 6700 KB Output is correct
5 Correct 2 ms 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 4 ms 7248 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 6 ms 7636 KB Output is correct
13 Correct 6 ms 7640 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 2 ms 6736 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 3 ms 6700 KB Output is correct
5 Correct 2 ms 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 4 ms 7248 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 6 ms 7636 KB Output is correct
13 Correct 6 ms 7640 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 2 ms 6736 KB Output is correct
16 Correct 645 ms 103468 KB Output is correct
17 Correct 55 ms 18504 KB Output is correct
18 Correct 99 ms 20684 KB Output is correct
19 Correct 766 ms 106660 KB Output is correct
20 Correct 510 ms 94568 KB Output is correct
21 Correct 33 ms 12872 KB Output is correct
22 Correct 418 ms 56132 KB Output is correct