oj.uz

Submission #589807

# Submission time Handle Problem Language Result Execution time Memory
589807 2022-07-05T09:47:50 Z Sam_a17 Shortcut (IOI16_shortcut) C++14
0 / 100
 0 ms 340 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "shortcut_c.h"
#include <cstdio>
using namespace std;
#define ll long long

const int N = 3e3 + 10;
const ll inf = 1e16;
long long maxLeft[N], maxRight[N];
long long maxLeftDiam[N], maxRightDiam[N];
set<pair<int, long long>> adj[N];
int ni;

pair<long long, long long> djik(int node) {
  vector<bool> used(ni + 1);
  vector<long long> dist(ni + 1, inf);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > q;
  dist[node] = 0;
  q.push({0, node});
 
  while(!q.empty()) {
    auto u = q.top();
    q.pop();

    if(used[u.second]) {
      continue;
    }
    used[u.second] = true;

    for(auto i: adj[u.second]) {
      if(dist[i.first] > dist[u.second] + i.second) {
        dist[i.first] = dist[u.second] + i.second;
        q.push({dist[i.first], i.first});
      }
    }
  }

  pair<ll, ll> answ = {-1, -1};

  for(int i = 0; i < ni; i++) {
    if(dist[i] > answ.first) {
      answ = {dist[i], i};
    }
  }

  return answ;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
  ni = n;


  if(d[0]) {
    adj[0].insert({ni, d[0]});
    adj[ni++].insert({0, d[0]});
  }

  for(int i = 1; i < n; i++) {
    adj[i - 1].insert({i, l[i - 1]});
    adj[i].insert({i - 1, l[i - 1]});

    if(d[i]) {
      adj[i].insert({ni, d[i]});
      adj[ni++].insert({i, d[i]});
    }
  }

  long long minDiametr = INT64_MAX;
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j < n; j++) {
      adj[i].insert({j, (long long)c});
      adj[j].insert({i, (long long)c});

      long long maxi = INT64_MIN;
      for(int k = 0; k < ni; k++) {
        maxi = max(maxi, djik(k).first);
      }

      minDiametr = min(maxi, minDiametr);

      adj[i].erase(adj[i].lower_bound(make_pair(j, (ll)c)));
      adj[j].erase(adj[j].lower_bound(make_pair(i, (ll)c)));
    }
  }

  return minDiametr;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -