oj.uz

Submission #751538

# Submission time Handle Problem Language Result Execution time Memory
751538 2023-05-31T17:21:34 Z somethingnew Cyberland (APIO23_cyberland) C++17
97 / 100
 1896 ms 277792 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, 35);
    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 88 ms 384 KB Correct.
2 Correct 83 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 4592 KB Correct.
2 Correct 382 ms 4420 KB Correct.
3 Correct 322 ms 4568 KB Correct.
4 Correct 362 ms 4348 KB Correct.
5 Correct 324 ms 5048 KB Correct.
6 Correct 427 ms 32572 KB Correct.
7 Correct 592 ms 27708 KB Correct.
8 Correct 241 ms 51168 KB Correct.
9 Correct 329 ms 772 KB Correct.
10 Correct 304 ms 752 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 4560 KB Correct.
2 Correct 511 ms 5072 KB Correct.
3 Correct 500 ms 4612 KB Correct.
4 Correct 377 ms 864 KB Correct.
5 Correct 404 ms 936 KB Correct.
6 Correct 122 ms 26296 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 170792 KB Correct.
2 Correct 334 ms 4752 KB Correct.
3 Correct 293 ms 4740 KB Correct.
4 Correct 324 ms 4556 KB Correct.
5 Correct 260 ms 728 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 4876 KB Correct.
2 Correct 282 ms 5268 KB Correct.
3 Correct 308 ms 5404 KB Correct.
4 Correct 407 ms 29240 KB Correct.
5 Correct 209 ms 744 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 5060 KB Correct.
2 Correct 326 ms 5456 KB Correct.
3 Correct 561 ms 197112 KB Correct.
4 Correct 320 ms 33988 KB Correct.
5 Correct 299 ms 812 KB Correct.
6 Correct 366 ms 5600 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 6208 KB Correct.
2 Correct 79 ms 7420 KB Correct.
3 Correct 882 ms 145396 KB Correct.
4 Correct 659 ms 43624 KB Correct.
5 Correct 1896 ms 236724 KB Correct.
6 Correct 1280 ms 188808 KB Correct.
7 Correct 583 ms 41668 KB Correct.
8 Correct 435 ms 8120 KB Correct.
9 Correct 389 ms 6568 KB Correct.
10 Correct 398 ms 6248 KB Correct.
11 Correct 439 ms 3572 KB Correct.
12 Correct 396 ms 6316 KB Correct.
13 Correct 411 ms 6628 KB Correct.
14 Correct 548 ms 41000 KB Correct.
15 Correct 523 ms 18520 KB Correct.
16 Correct 423 ms 6744 KB Correct.
17 Correct 446 ms 6600 KB Correct.
18 Correct 438 ms 6936 KB Correct.
19 Correct 864 ms 10824 KB Correct.
20 Correct 29 ms 860 KB Correct.
21 Correct 29 ms 4052 KB Correct.
22 Correct 97 ms 21892 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 6776 KB Correct.
2 Correct 89 ms 8744 KB Correct.
3 Incorrect 621 ms 277792 KB Wrong Answer.
4 Halted 0 ms 0 KB -