oj.uz

Submission #981946

# Submission time Handle Problem Language Result Execution time Memory
981946 2024-05-13T16:59:32 Z kilkuwu Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 4468 KB 
#include "crocodile.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

template <typename T> 
std::pair<T, T> operator-(std::pair<T, T> x) {
  return {-x.first, -x.second};
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
#define int int64_t
  std::vector<std::vector<std::pair<int, int>>> adj(N);

  for (int i = 0; i < M; i++) {
    int u = R[i][0], v = R[i][1], w = L[i];
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  std::vector<std::pair<int, int>> dp(N, {1e18, 1e18});

  std::priority_queue<std::pair<std::pair<int, int>, int>> pq;

  for (int i = 0; i < K; i++) {
    dp[P[i]] = {0, 0};
    pq.emplace(dp[P[i]], P[i]);
  }

  auto update = [&](int u, int len) -> bool {
    if (len < dp[u].first) {
      dp[u].second = dp[u].first;
      dp[u].first = len;
      return true;
    } else if (len < dp[u].second) {
      dp[u].second = len;
      return true;
    }
    return false;
  };

  // sort by fastest first ?  

  while (pq.size()) {
    auto [d, u] = pq.top();
    pq.pop();

    d = -d;

    if (d > dp[u]) continue;

    for (auto [v, w] : adj[u]) {
      if (update(v, d.second + w)) {
        pq.emplace(-dp[v], v);
      }  
    }
  }


  assert(dp[0].second <= 1e9);
  return dp[0].second;
#undef int
}



#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}

#endif

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4468 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4468 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4468 KB Output isn't correct
4 Halted 0 ms 0 KB -