oj.uz

Submission #751537

# Submission time Handle Problem Language Result Execution time Memory
751537 2023-05-31T17:20:08 Z somethingnew Cyberland (APIO23_cyberland) C++17
97 / 100
 2984 ms 254440 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, 32);
    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 92 ms 472 KB Correct.
2 Correct 89 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 4640 KB Correct.
2 Correct 529 ms 4460 KB Correct.
3 Correct 524 ms 4568 KB Correct.
4 Correct 509 ms 4364 KB Correct.
5 Correct 511 ms 4988 KB Correct.
6 Correct 625 ms 32632 KB Correct.
7 Correct 811 ms 27760 KB Correct.
8 Correct 322 ms 51268 KB Correct.
9 Correct 411 ms 832 KB Correct.
10 Correct 414 ms 724 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 4700 KB Correct.
2 Correct 714 ms 5120 KB Correct.
3 Correct 703 ms 4768 KB Correct.
4 Correct 576 ms 792 KB Correct.
5 Correct 542 ms 928 KB Correct.
6 Correct 167 ms 26276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 175768 KB Correct.
2 Correct 488 ms 4580 KB Correct.
3 Correct 435 ms 4564 KB Correct.
4 Correct 463 ms 4968 KB Correct.
5 Correct 378 ms 756 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 4796 KB Correct.
2 Correct 432 ms 5544 KB Correct.
3 Correct 425 ms 5448 KB Correct.
4 Correct 612 ms 29384 KB Correct.
5 Correct 299 ms 760 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 5252 KB Correct.
2 Correct 490 ms 5508 KB Correct.
3 Correct 620 ms 197240 KB Correct.
4 Correct 446 ms 34836 KB Correct.
5 Correct 435 ms 848 KB Correct.
6 Correct 564 ms 5784 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 6252 KB Correct.
2 Correct 117 ms 8068 KB Correct.
3 Correct 1279 ms 146236 KB Correct.
4 Correct 916 ms 43604 KB Correct.
5 Correct 2984 ms 236644 KB Correct.
6 Correct 2399 ms 192944 KB Correct.
7 Correct 901 ms 41760 KB Correct.
8 Correct 691 ms 8000 KB Correct.
9 Correct 609 ms 7040 KB Correct.
10 Correct 569 ms 6532 KB Correct.
11 Correct 641 ms 3492 KB Correct.
12 Correct 644 ms 6104 KB Correct.
13 Correct 638 ms 6688 KB Correct.
14 Correct 809 ms 41220 KB Correct.
15 Correct 749 ms 18552 KB Correct.
16 Correct 613 ms 6044 KB Correct.
17 Correct 696 ms 6804 KB Correct.
18 Correct 682 ms 6984 KB Correct.
19 Correct 1342 ms 10748 KB Correct.
20 Correct 45 ms 808 KB Correct.
21 Correct 46 ms 4140 KB Correct.
22 Correct 170 ms 22456 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 6380 KB Correct.
2 Correct 120 ms 8416 KB Correct.
3 Incorrect 758 ms 254440 KB Wrong Answer.
4 Halted 0 ms 0 KB -