oj.uz

Submission #773388

# Submission time Handle Problem Language Result Execution time Memory
773388 2023-07-05T03:43:42 Z Jomnoi Shortcut (IOI16_shortcut) C++17
0 / 100
 40 ms 94156 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

const int MAX_N = 2e6 + 5;
const long long INF = 1e18 + 7;

int n;
set <pair <int, int>> graph[MAX_N];
long long dist[MAX_N];
bool visited[MAX_N];

void bfs(int s) {
    for (int i = 0; i < 2 * n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    priority_queue <pair <long long, int>> pq;
    pq.emplace(0, s);
    dist[s] = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u] == true) continue;
        visited[u] = true;

        for (auto [v, w] : graph[u]) {
            if (visited[v] == false and dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(-dist[v], v);
            }
        }
    }
}

long long find_shortcut(int n, vector <int> l, vector <int> d, int c) {
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        graph[i].emplace(i + 1, l[i]);
        graph[i + 1].emplace(i, l[i]);
    }
    for (int i = 0; i < n; i++) {
        graph[i].emplace(n + i, d[i]);
        graph[n + i].emplace(i, d[i]);
    }

    long long ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            bool ok = false;

            if (!graph[i].count(make_pair(j, c))) {
                ok = true;
                graph[i].emplace(j, c);
                graph[j].emplace(i, c);
            }

            bfs(0);

            long long max_dist = 0;
            int st = -1;
            for (int i = 0; i < 2 * n; i++) {
                if (max_dist < dist[i]) {
                    max_dist = dist[i];
                    st = i;
                }
            }


            bfs(st);

            max_dist = 0;
            for (int i = 0; i < 2 * n; i++) max_dist = max(max_dist, dist[i]);

            ans = min(ans, max_dist);

            if (ok == true) {
                graph[i].erase(make_pair(j, c));
                graph[j].erase(make_pair(i, c));
            }
        }
    }
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94156 KB n = 4, 80 is a correct answer
2 Incorrect 39 ms 94132 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -