oj.uz

Submission #1105312

# Submission time Handle Problem Language Result Execution time Memory
1105312 2024-10-26T06:29:05 Z Zone_zonee Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 798 ms 123024 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]);
  }
  fill(dis, dis+N, 1e18);
  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(dis[u] != 1e18) continue;
    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 2 ms 6480 KB Output is correct
5 Correct 2 ms 6648 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 2 ms 6480 KB Output is correct
5 Correct 2 ms 6648 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 7216 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 2 ms 6584 KB Output is correct
12 Correct 6 ms 7636 KB Output is correct
13 Correct 6 ms 7640 KB Output is correct
14 Correct 2 ms 6480 KB Output is correct
15 Correct 2 ms 6480 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 2 ms 6480 KB Output is correct
5 Correct 2 ms 6648 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 7216 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 2 ms 6584 KB Output is correct
12 Correct 6 ms 7636 KB Output is correct
13 Correct 6 ms 7640 KB Output is correct
14 Correct 2 ms 6480 KB Output is correct
15 Correct 2 ms 6480 KB Output is correct
16 Correct 720 ms 103596 KB Output is correct
17 Correct 59 ms 18636 KB Output is correct
18 Correct 96 ms 24136 KB Output is correct
19 Correct 798 ms 123024 KB Output is correct
20 Correct 468 ms 107508 KB Output is correct
21 Correct 34 ms 14160 KB Output is correct
22 Correct 418 ms 70328 KB Output is correct