oj.uz

Submission #751542

# Submission time Handle Problem Language Result Execution time Memory
751542 2023-05-31T17:24:39 Z somethingnew Cyberland (APIO23_cyberland) C++17
97 / 100
 2114 ms 324688 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, 40 + (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 94 ms 436 KB Correct.
2 Correct 95 ms 568 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 4592 KB Correct.
2 Correct 398 ms 4420 KB Correct.
3 Correct 397 ms 4604 KB Correct.
4 Correct 432 ms 4344 KB Correct.
5 Correct 407 ms 5020 KB Correct.
6 Correct 453 ms 32560 KB Correct.
7 Correct 679 ms 27692 KB Correct.
8 Correct 254 ms 51212 KB Correct.
9 Correct 311 ms 696 KB Correct.
10 Correct 328 ms 752 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 4552 KB Correct.
2 Correct 549 ms 5088 KB Correct.
3 Correct 524 ms 4612 KB Correct.
4 Correct 442 ms 976 KB Correct.
5 Correct 392 ms 916 KB Correct.
6 Correct 143 ms 26252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 170684 KB Correct.
2 Correct 399 ms 4708 KB Correct.
3 Correct 363 ms 4728 KB Correct.
4 Correct 361 ms 4524 KB Correct.
5 Correct 306 ms 740 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 4788 KB Correct.
2 Correct 318 ms 5256 KB Correct.
3 Correct 312 ms 5456 KB Correct.
4 Correct 456 ms 29300 KB Correct.
5 Correct 224 ms 724 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 5208 KB Correct.
2 Correct 367 ms 5512 KB Correct.
3 Correct 666 ms 197024 KB Correct.
4 Correct 355 ms 33992 KB Correct.
5 Correct 334 ms 948 KB Correct.
6 Correct 459 ms 5712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 6192 KB Correct.
2 Correct 84 ms 7416 KB Correct.
3 Correct 1004 ms 145436 KB Correct.
4 Correct 750 ms 43736 KB Correct.
5 Correct 2114 ms 236720 KB Correct.
6 Correct 1494 ms 188916 KB Correct.
7 Correct 633 ms 41768 KB Correct.
8 Correct 476 ms 8008 KB Correct.
9 Correct 444 ms 6528 KB Correct.
10 Correct 403 ms 6236 KB Correct.
11 Correct 458 ms 3504 KB Correct.
12 Correct 469 ms 6344 KB Correct.
13 Correct 448 ms 6648 KB Correct.
14 Correct 614 ms 41076 KB Correct.
15 Correct 471 ms 18528 KB Correct.
16 Correct 463 ms 6708 KB Correct.
17 Correct 475 ms 6664 KB Correct.
18 Correct 479 ms 6924 KB Correct.
19 Correct 1029 ms 10700 KB Correct.
20 Correct 31 ms 724 KB Correct.
21 Correct 32 ms 4040 KB Correct.
22 Correct 114 ms 21940 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 8172 KB Correct.
2 Correct 112 ms 9912 KB Correct.
3 Incorrect 690 ms 324688 KB Wrong Answer.
4 Halted 0 ms 0 KB -