oj.uz

Submission #999540

# Submission time Handle Problem Language Result Execution time Memory
999540 2024-06-15T17:46:55 Z Mr_Husanboy Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 309 ms 71108 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long

template<typename T>
int len(T &a){return a.size();}
const int inf = 1e9 + 1;
const ll infl = 1e18 + 1;
#define ss second
#define ff first
#define all(a) (a).begin(), (a).end()


int travel_plan(int n, int m, int r[][2], int L[], int K, int P[])
{
  vector<vector<pair<int,int>>> g(n);
  //cout << "done" << endl;
  for(int i = 0; i < m; i ++){
    g[r[i][0]].push_back({r[i][1], L[i]});
    g[r[i][1]].push_back({r[i][0], L[i]});
  }
  
  vector<pair<ll, ll>> dis(n, {infl, infl});
  priority_queue<pair<ll, int>> q;
  for(int i = 0; i < K; i ++){
    q.push({0, P[i]});
    dis[P[i]] = {0, 0};
  }
  vector<int> vis(n);

  while(!q.empty()){
    int t = q.top().ss;
    q.pop();
    if(vis[t]) continue;
    vis[t] = 1;
    for(auto [u, w] : g[t]){
      if(dis[u].ff > dis[t].ss + w){
        dis[u].ss = dis[u].ff;
        q.push({-dis[u].ss, u});
        dis[u].ff = dis[t].ss + w;
      }else if(dis[u].ss > dis[t].ss + w){
        dis[u].ss = dis[t].ss + w;
        q.push({-dis[u].ss, u});
      }
    }
  }
  return dis[0].ss;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 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 1 ms 4444 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 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 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 1 ms 4548 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 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 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 1 ms 4548 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 242 ms 60612 KB Output is correct
17 Correct 55 ms 18888 KB Output is correct
18 Correct 68 ms 20172 KB Output is correct
19 Correct 309 ms 71108 KB Output is correct
20 Correct 154 ms 47904 KB Output is correct
21 Correct 26 ms 10196 KB Output is correct
22 Correct 184 ms 47140 KB Output is correct