oj.uz

Submission #1074348

# Submission time Handle Problem Language Result Execution time Memory
1074348 2024-08-25T09:57:56 Z dosts Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 4444 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define int long long
#define ii int32_t
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int inf = 2e12;
ii travel_plan(ii N, ii M, ii R[][2], ii L[], ii K, ii P[])
{
  vector<pii> edges[N];
  for (int i=0;i<M;i++) {
    edges[R[i][0]].push_back({R[i][1],L[i]});
    edges[R[i][1]].push_back({R[i][0],L[i]});
  }
  pii dist[N];
  for (int i=0;i<N;i++) dist[i] = {inf,inf};
  using state = pair<pii,int>;
  priority_queue<state,vector<state>,greater<state>> pq;
  for (int i=0;i<K;i++) {
    dist[P[i]] = {0,0};
    pq.push({{0,0},P[i]});
  }
  while (!pq.empty()) {
    state f = pq.top();
    pq.pop();
    if (f.ff > dist[f.ss]) continue;
    for (auto it : edges[f.ss]) {
      int go = it.ff,w = it.ss;
      pii pp = dist[go];
      int newval = f.ff.ss+w;
      if (newval < pp.ff) {
        pp.ss = pp.ff;
        pp.ff = newval;
      }
      else if (newval < pp.ss) {
        pp.ss = newval;
      }
      bool better = 0;
      if (pp.ss < dist[go].ss) better = 1;
      else if (pp.ff < dist[go].ff) better = 1;
      if (better) {
        dist[go] = pp;
        state pusher = make_pair(dist[go],go);
        if (dist[go].ss < inf) pq.push(pusher);
      } 
    }
  }
  return dist[0].ss;
}

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 4444 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 4444 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 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -