oj.uz

Submission #952191

# Submission time Handle Problem Language Result Execution time Memory
952191 2024-03-23T09:21:14 Z emad234 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 396 ms 94244 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 = 2e6 + 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[])
{
  memset(mn, -1, sizeof mn);
  v.resize(N + 2);
  for (ll i = 0; i < N; i++)
  {
    dist[i] = 1e9 + 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++)
  {
    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 && mn[x.F] == -1)
      {
        mn[x.F] = x.S + u.F;
      }
      else if (dist[x.F] > x.S + u.F && mn[x.F] != -1)
      {
        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
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 3 ms 21080 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 6 ms 21340 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Correct 5 ms 21120 KB Output is correct
12 Correct 6 ms 21592 KB Output is correct
13 Correct 6 ms 21596 KB Output is correct
14 Correct 3 ms 21112 KB Output is correct
15 Correct 4 ms 21084 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 3 ms 21080 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 6 ms 21340 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Correct 5 ms 21120 KB Output is correct
12 Correct 6 ms 21592 KB Output is correct
13 Correct 6 ms 21596 KB Output is correct
14 Correct 3 ms 21112 KB Output is correct
15 Correct 4 ms 21084 KB Output is correct
16 Correct 314 ms 86044 KB Output is correct
17 Correct 55 ms 33444 KB Output is correct
18 Correct 70 ms 35508 KB Output is correct
19 Correct 396 ms 94244 KB Output is correct
20 Correct 240 ms 73900 KB Output is correct
21 Correct 30 ms 25944 KB Output is correct
22 Incorrect 235 ms 66232 KB Output isn't correct
23 Halted 0 ms 0 KB -