oj.uz

Submission #751533

# Submission time Handle Problem Language Result Execution time Memory
751533 2023-05-31T17:11:06 Z somethingnew Cyberland (APIO23_cyberland) C++17
44 / 100
 1901 ms 190772 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)
            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] < 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;
        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, 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 4436 KB Correct.
2 Correct 856 ms 4352 KB Correct.
3 Correct 847 ms 4524 KB Correct.
4 Correct 886 ms 4284 KB Correct.
5 Correct 894 ms 4836 KB Correct.
6 Correct 953 ms 31604 KB Correct.
7 Correct 1332 ms 26844 KB Correct.
8 Correct 502 ms 49648 KB Correct.
9 Correct 698 ms 844 KB Correct.
10 Correct 641 ms 852 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 4748 KB Correct.
2 Correct 1077 ms 5024 KB Correct.
3 Correct 1028 ms 4780 KB Correct.
4 Correct 852 ms 868 KB Correct.
5 Correct 864 ms 912 KB Correct.
6 Correct 261 ms 25700 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1901 ms 170548 KB Correct.
2 Incorrect 1027 ms 4436 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 4712 KB Correct.
2 Correct 715 ms 5152 KB Correct.
3 Correct 701 ms 5460 KB Correct.
4 Correct 993 ms 28468 KB Correct.
5 Correct 510 ms 752 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 5124 KB Correct.
2 Correct 746 ms 5532 KB Correct.
3 Correct 652 ms 190772 KB Correct.
4 Correct 739 ms 33956 KB Correct.
5 Correct 625 ms 884 KB Correct.
6 Correct 833 ms 5632 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1180 ms 6148 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1170 ms 6052 KB Wrong Answer.
2 Halted 0 ms 0 KB -