oj.uz

Submission #449871

# Submission time Handle Problem Language Result Execution time Memory
449871 2021-08-02T08:51:24 Z Karliver Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 726 ms 63884 KB 
#include "crocodile.h"
  
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 100;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


V<pairs> g[N];
int dis[N][2];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
  forn(i, n) dis[i][0] = dis[i][1] = INF;
  forn(i, m) {
    g[R[i][0]].emplace_back(R[i][1], L[i]);
    g[R[i][1]].emplace_back(R[i][0], L[i]);
  }

  priority_queue<pairs, V<pairs>, greater<pairs>> q;
  V<int> vis(n, 0);
  
  forn(i, K) {
    q.emplace(0, P[i]);
    vis[P[i]] = 1;
    dis[P[i]][0] = dis[P[i]][1] = 0;
  }

  while(q.size()) {
    auto [s, v] = q.top();
    q.pop();

    if(vis[v] == 2)continue;
    ++vis[v];
    if(vis[v] == 1)continue;
    for(auto [i, w] : g[v]) {
      int x = s + w;
      

      if(x < dis[i][0]) {
        swap(dis[i][1], dis[i][0]);
        dis[i][0] = x;
        q.emplace(x, i);
      }
      else if(x < dis[i][1]) {
        dis[i][1] = x;
        q.emplace(x, i);
      } 
    }
  }

  return dis[0][1];



}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:52:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     auto [s, v] = q.top();
      |          ^
crocodile.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [i, w] : g[v]) {
      |              ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4980 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 4 ms 5012 KB Output is correct
5 Correct 4 ms 5020 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5016 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4980 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 4 ms 5012 KB Output is correct
5 Correct 4 ms 5020 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5016 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 5016 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 10 ms 5452 KB Output is correct
14 Correct 6 ms 5008 KB Output is correct
15 Correct 5 ms 5012 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4980 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 4 ms 5012 KB Output is correct
5 Correct 4 ms 5020 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5016 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 5016 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 10 ms 5452 KB Output is correct
14 Correct 6 ms 5008 KB Output is correct
15 Correct 5 ms 5012 KB Output is correct
16 Correct 500 ms 60864 KB Output is correct
17 Correct 89 ms 16400 KB Output is correct
18 Correct 109 ms 17912 KB Output is correct
19 Correct 726 ms 63884 KB Output is correct
20 Correct 413 ms 51832 KB Output is correct
21 Correct 44 ms 10132 KB Output is correct
22 Correct 381 ms 48412 KB Output is correct