oj.uz

Submission #751544

# Submission time Handle Problem Language Result Execution time Memory
751544 2023-05-31T17:27:00 Z somethingnew Cyberland (APIO23_cyberland) C++17
97 / 100
 1920 ms 512644 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])
            if (res[i.first] > 1e17)
                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])
            if (res[i.first] > 1e17)
                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, 64 + (K+1) % 2);
    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:27: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]
   27 |     for (int i = 0; i < g.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 460 KB Correct.
2 Correct 86 ms 404 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 4580 KB Correct.
2 Correct 351 ms 4444 KB Correct.
3 Correct 330 ms 4672 KB Correct.
4 Correct 356 ms 4348 KB Correct.
5 Correct 357 ms 4988 KB Correct.
6 Correct 398 ms 32656 KB Correct.
7 Correct 612 ms 27708 KB Correct.
8 Correct 222 ms 51148 KB Correct.
9 Correct 269 ms 696 KB Correct.
10 Correct 268 ms 872 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 4492 KB Correct.
2 Correct 435 ms 5048 KB Correct.
3 Correct 483 ms 4648 KB Correct.
4 Correct 379 ms 948 KB Correct.
5 Correct 391 ms 968 KB Correct.
6 Correct 139 ms 26300 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 170784 KB Correct.
2 Correct 352 ms 4728 KB Correct.
3 Correct 343 ms 4796 KB Correct.
4 Correct 332 ms 4520 KB Correct.
5 Correct 265 ms 728 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 4824 KB Correct.
2 Correct 325 ms 5228 KB Correct.
3 Correct 327 ms 5452 KB Correct.
4 Correct 434 ms 29232 KB Correct.
5 Correct 226 ms 776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 5052 KB Correct.
2 Correct 312 ms 5400 KB Correct.
3 Correct 667 ms 197144 KB Correct.
4 Correct 303 ms 33920 KB Correct.
5 Correct 293 ms 880 KB Correct.
6 Correct 360 ms 5716 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 6200 KB Correct.
2 Correct 85 ms 7456 KB Correct.
3 Correct 909 ms 145388 KB Correct.
4 Correct 693 ms 43756 KB Correct.
5 Correct 1920 ms 236732 KB Correct.
6 Correct 1399 ms 188920 KB Correct.
7 Correct 649 ms 41728 KB Correct.
8 Correct 476 ms 8068 KB Correct.
9 Correct 416 ms 6568 KB Correct.
10 Correct 427 ms 6236 KB Correct.
11 Correct 446 ms 3492 KB Correct.
12 Correct 398 ms 6352 KB Correct.
13 Correct 412 ms 6604 KB Correct.
14 Correct 566 ms 41016 KB Correct.
15 Correct 508 ms 18524 KB Correct.
16 Correct 397 ms 6656 KB Correct.
17 Correct 499 ms 6632 KB Correct.
18 Correct 451 ms 6944 KB Correct.
19 Correct 901 ms 10716 KB Correct.
20 Correct 32 ms 724 KB Correct.
21 Correct 31 ms 3988 KB Correct.
22 Correct 108 ms 21856 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 12836 KB Correct.
2 Correct 168 ms 14952 KB Correct.
3 Incorrect 1179 ms 512644 KB Wrong Answer.
4 Halted 0 ms 0 KB -