oj.uz

Submission #1025928

# Submission time Handle Problem Language Result Execution time Memory
1025928 2024-07-17T11:21:45 Z NguyenPhucThang Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 351 ms 92608 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
#define oo 1e18
using namespace std;


ll travel_plan(int n, int m, int R[][2], int L[], int k, int p[]){
   vector<vector<pll>> g(n + 1);
   vector<bool> checked(n + 1);
   vector<vector<ll>> d(n + 1, vector<ll>(2));

   priority_queue<pll, vector<pll>, greater<pll>> pq;

   forf(i, 0, n) d[i][0] = d[i][1] = oo;

   forf(i, 0, m){
      ll x = R[i][0], y = R[i][1], w = L[i];
      g[x].pb({y, w});
      g[y].pb({x, w});
   }

   forf(i, 0, n) d[i][0] = d[i][1] = oo;

   forf(i, 0, k){
      d[p[i]][0] = d[p[i]][1] = 0;
      pq.push({d[p[i]][1], p[i]});
   }

   while (!pq.empty()){
      pll x = pq.top();
      pq.pop();
      int u = x.se;
      
      if (checked[u]) continue;
      checked[u] = true;

      for(pll e : g[u]){
         ll v = e.fi, w = e.se;
         if (d[v][0] > d[u][1] + w){
            if (d[v][0] != d[v][1] && d[v][0] < oo){
               d[v][1] = d[v][0];
               pq.push({d[v][1], v});
            }
            d[v][0] = d[u][1] + w;
         }
         else if (d[v][1] > d[u][1] + w){
            d[v][1] = d[u][1] + w;
            pq.push({d[v][1], v});
         }
      }
   }

   return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 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 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4568 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 ms 3064 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 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 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4568 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 ms 3064 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 274 ms 82460 KB Output is correct
17 Correct 55 ms 22964 KB Output is correct
18 Correct 68 ms 25684 KB Output is correct
19 Correct 351 ms 92608 KB Output is correct
20 Correct 193 ms 65072 KB Output is correct
21 Correct 25 ms 11096 KB Output is correct
22 Correct 210 ms 63316 KB Output is correct