oj.uz

Submission #751536

# Submission time Handle Problem Language Result Execution time Memory
751536 2023-05-31T17:18:30 Z somethingnew Cyberland (APIO23_cyberland) C++17
97 / 100
 2776 ms 238584 KB 
#include "cyberland.h"
#include "queue"

#include <vector>
using namespace std;
vector<vector<pair<int, double>>> g;
vector<int> slv1(vector<int> arr, int n, int k, int h) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> que;
    for (int i = 0; i < k; ++i) {
        que.push({0, i * n});
    }
    vector<double> res(g.size(), 1e18);
    while (!que.empty()) {
        auto [prc, v] = que.top();
        que.pop();
        if (v % n == h or v >= n)
            continue;
        if (1e17 > res[v])
            continue;
        //cout << prc << ' ' << v << '\n';
        res[v] = prc;
        for (auto i : g[v])
            que.push({prc + i.second, i.first});
    }
    vector<int> reska;
    for (int i = 0; i < g.size(); ++i) {
        if (res[i % n] < 1e17 and arr[i % n] == 0)
            reska.push_back(i);
    }
    return reska;
}
double slv2(int n, int k, int h, vector<int> tork) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> que;
    for (auto i : tork) {
        que.push({0, i});
    }
    vector<double> res(g.size(), 1e18);
    while (!que.empty()) {
        auto [prc, v] = que.top();
        que.pop();
        if (1e17 > res[v])
            continue;
        //cout << prc << ' ' << v << '\n';
        res[v] = prc;
        if (v % n == h)
            continue;
        for (auto i : g[v])
            que.push({prc + i.second, i.first});
    }
    return res[n * k - n + h];
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K+1, 30);
    int kn = K * N;
    //cout << kn << '\n';
    g.assign(kn, {});
    double dv = 1;
    for (int j = K - 1; j >= 0; --j) {
        for (int i = 0; i < M; ++i) {
            int a = x[i], b = y[i], tm = c[i];
            int isa = arr[a];
            a += j * N;
            b += j * N;
            g[a].push_back({b, tm / dv});
            if (isa == 2) {
                if (j + 1 != K)
                    g[a].push_back({b + N, tm * 2 / dv});
            }
            a = y[i], b = x[i], tm = c[i];
            isa = arr[a];
            a += j * N;
            b += j * N;
            g[a].push_back({b, tm / dv});
            if (isa == 2) {
                if (j + 1 != K)
                    g[a].push_back({b + N, tm * 2 / dv});
            }
        }
        dv *= 2;
    }
    arr[0] = 0;
    vector<int> tor2 = slv1(arr, N, K, H);
    double res = slv2(N, K, H, tor2);
    if (res > 1e17)
        return -1;
    return res;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 444 KB Correct.
2 Correct 86 ms 556 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 4448 KB Correct.
2 Correct 503 ms 4336 KB Correct.
3 Correct 496 ms 4468 KB Correct.
4 Correct 526 ms 4272 KB Correct.
5 Correct 549 ms 4848 KB Correct.
6 Correct 546 ms 31632 KB Correct.
7 Correct 770 ms 26780 KB Correct.
8 Correct 302 ms 49612 KB Correct.
9 Correct 405 ms 696 KB Correct.
10 Correct 394 ms 980 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 4556 KB Correct.
2 Correct 735 ms 5048 KB Correct.
3 Correct 670 ms 4836 KB Correct.
4 Correct 531 ms 900 KB Correct.
5 Correct 531 ms 868 KB Correct.
6 Correct 188 ms 25588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 170432 KB Correct.
2 Correct 515 ms 4336 KB Correct.
3 Correct 404 ms 4280 KB Correct.
4 Correct 475 ms 4444 KB Correct.
5 Correct 393 ms 752 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 4724 KB Correct.
2 Correct 426 ms 5124 KB Correct.
3 Correct 414 ms 5256 KB Correct.
4 Correct 596 ms 28548 KB Correct.
5 Correct 291 ms 712 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 5236 KB Correct.
2 Correct 486 ms 5376 KB Correct.
3 Correct 590 ms 190880 KB Correct.
4 Correct 473 ms 33852 KB Correct.
5 Correct 426 ms 856 KB Correct.
6 Correct 516 ms 5668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 6124 KB Correct.
2 Correct 110 ms 7852 KB Correct.
3 Correct 1312 ms 146280 KB Correct.
4 Correct 888 ms 43628 KB Correct.
5 Correct 2776 ms 230652 KB Correct.
6 Correct 2286 ms 188044 KB Correct.
7 Correct 899 ms 41840 KB Correct.
8 Correct 692 ms 7992 KB Correct.
9 Correct 628 ms 6768 KB Correct.
10 Correct 569 ms 6384 KB Correct.
11 Correct 645 ms 3528 KB Correct.
12 Correct 628 ms 5952 KB Correct.
13 Correct 664 ms 6408 KB Correct.
14 Correct 844 ms 41004 KB Correct.
15 Correct 813 ms 18516 KB Correct.
16 Correct 643 ms 5924 KB Correct.
17 Correct 693 ms 6552 KB Correct.
18 Correct 696 ms 6700 KB Correct.
19 Correct 1334 ms 10532 KB Correct.
20 Correct 43 ms 840 KB Correct.
21 Correct 44 ms 3948 KB Correct.
22 Correct 169 ms 21848 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 6132 KB Correct.
2 Correct 114 ms 7880 KB Correct.
3 Incorrect 693 ms 238584 KB Wrong Answer.
4 Halted 0 ms 0 KB -