oj.uz

Submission #575512

# Submission time Handle Problem Language Result Execution time Memory
575512 2022-06-10T20:07:47 Z Elias Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 300 KB 
#include <bits/stdc++.h>

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include "shortcut.h"
#endif

using namespace std;

vector<vector<pair<int, int>>> adj;

vector<int> dijkstra(int s)
{
    vector<int> dist(adj.size(), -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});

    while (!pq.empty())
    {
        auto [d, i] = pq.top();
        pq.pop();

        if (dist[i] != -1)
            continue;

        dist[i] = d;

        for (auto [c, p] : adj[i])
        {
            if (dist[c] == -1)
                pq.push({d + p, c});
        }
    }

    return dist;
}

long long dia()
{
    int longest = 0;
    for (int i = 0; i < adj.size(); i++)
    {
        vector<int> dists;
        dists = dijkstra(i);
        longest = max(longest, *max_element(dists.begin(), dists.end()));
    }

    return longest;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    adj = vector<vector<pair<int, int>>>(2 * n);

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

    for (int i = 0; i < n; i++)
    {
        adj[i].push_back({i + n, d[i]});
        adj[i + n].push_back({i, d[i]});
    }

    long long best = dia();

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

            best = min(best, dia());

            adj[i].pop_back();
            adj[j].pop_back();
        }

    return best;
}

#ifdef _DEBUG

int main()
{
    int n, c;
    cin >> n >> c;

    vector<int> l(n - 1);
    vector<int> d(n);

    for (int &x : l)
        cin >> x;

    for (int &x : d)
        cin >> x;

    cout << find_shortcut(n, l, d, c);
}

#endif

Compilation message

shortcut.cpp: In function 'long long int dia()':
shortcut.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~

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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 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 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 300 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 1 ms 212 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 2000000001 vs contestant 2000000000
11 Halted 0 ms 0 KB -