oj.uz

Submission #952237

# Submission time Handle Problem Language Result Execution time Memory
952237 2024-03-23T10:37:37 Z emad234 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 6588 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
vector<vector<pii>> v;
ll dist[mxN], mn[mxN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  v.clear();
  v.resize(N + 3);
  for (ll i = 0; i < N; i++)
  {
    dist[i] = 1e18 + 5;
    mn[i] = 1e18 + 5;
  }
  for (ll i = 0; i < M; i++)
  {
    v[R[i][1]].push_back({R[i][0], L[i]});
    v[R[i][0]].push_back({R[i][1], L[i]});
  }
  priority_queue<pii, vector<pii>, greater<pii>> q;
  for (ll i = 0; i < K; i++)
  {
    mn[P[i]] = 0;
    dist[P[i]] = 0;
    q.push({0, P[i]});
  }
  while (q.size())
  {
    auto u = q.top();
    q.pop();
    // if (dist[u.S] < u.F)
    //   continue;
    for (auto x : v[u.S])
    {
      if (dist[x.F] > x.S + u.F)
      {
        ll Mn = mn[x.F];
        mn[x.F] = min(x.S + u.F, Mn);
        dist[x.F] = max(x.S + u.F, Mn);
        q.push({dist[x.F], x.F});
      }
    }
  }
  return dist[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6588 KB Output isn't correct
4 Halted 0 ms 0 KB -