oj.uz

Submission #798874

# Submission time Handle Problem Language Result Execution time Memory
798874 2023-07-31T06:05:03 Z NeroZein Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 296 KB 
#include "bits/stdc++.h"
#include "shortcut.h"

using namespace std;

const long long INF = 1e15;

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
  auto dij = [&](int src, vector<vector<pair<int, int>>>& g) {
    vector<long long> dis(n, INF);
    dis[src] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; 
    pq.emplace(0, src);
    long long ret = 0;
    while (!pq.empty()) {
      auto [cur, v] = pq.top();
      pq.pop();
      if (cur != dis[v]) continue;
      ret = max(ret, cur + d[v]); 
      for (auto [u, w] : g[v]) {
        if (cur + w < dis[u]) {
          dis[u] = cur + w;
          pq.emplace(dis[u], u); 
        }
      }
    }
    ret += d[src];
    return ret;
  };
  auto get = [&](int i, int j, vector<vector<pair<int, int>>> g) {
    g[i].emplace_back(j, c);
    g[j].emplace_back(i, c);
    long long ret = 0;
    for (int v = 0; v < n; ++v) {
      ret = max(ret, dij(v, g));
    }
    return ret;
  }; 
  vector<vector<pair<int, int>>> g(n);
  g[0].emplace_back(1, l[0]);
  for (int i = 1; i < n - 1; ++i) {
    g[i].emplace_back(i - 1, l[i - 1]);
    g[i].emplace_back(i + 1, l[i]); 
  }
  g[n - 1].emplace_back(n - 2, l[n - 2]);
  long long ans = INF;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      ans = min(ans, get(i, j, g));
    }
  }
  return ans; 
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 296 KB n = 4, 21 is a correct answer
4 Correct 0 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -