oj.uz

Submission #1065866

# Submission time Handle Problem Language Result Execution time Memory
1065866 2024-08-19T12:26:51 Z yanndev Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 163484 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Edge {
    int to;
    int dst;
};

struct Node {
    int at;
    int op2;
    double dst;
    bool operator<(const Node& other) const {
        if (dst != other.dst)
            return dst > other.dst;
        if (at != other.at)
            return at < other.at;
        return op2 < other.op2;
    }
};

void initDfs(int node, vector<vector<Edge>>& adj, vector<bool>& vis, int H) {
    vis[node] = true;
    for (auto& x: adj[node])
        if (x.to != H && !vis[x.to])
            initDfs(x.to, adj, vis, 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, 77);

    vector<vector<Edge>> adj (N);

    for (int i = 0; i < M; i++) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    vector<vector<double>> dist (N);
    for (int i = 0; i < N; i++)
        dist[i].assign(K + 1, 1e18);

    vector<bool> vis (N, false);
    initDfs(0, adj, vis, H);

    priority_queue<Node> nxt {};

    arr[0] = 0;
    for (int i = 0; i < N; i++) {
        if (vis[i] && arr[i] == 0) {
            dist[i][0] = 0;
            nxt.push({i, 0, 0});
        }
    }

    while (!nxt.empty()) {
        auto cur = nxt.top();
        nxt.pop();

        if (cur.at == H)
            continue;

        if (dist[cur.at][cur.op2] == cur.dst) {
            for (auto& x: adj[cur.at]) {
                // no divide
                double nxtDst = cur.dst + (double)x.dst;
                if (nxtDst < dist[x.to][cur.op2]) {
                    dist[x.to][cur.op2] = nxtDst;
                    nxt.push({x.to, cur.op2, nxtDst});
                }

                // use divide
                nxtDst /= 2;
                if (arr[x.to] == 2 && cur.op2 < K && nxtDst < dist[x.to][cur.op2 + 1]) {
                    dist[x.to][cur.op2 + 1] = nxtDst;
                    nxt.push({x.to, cur.op2 + 1, nxtDst});   
                }
            }
        }
    }

    double ans = 1e18;
    for (int i = 0; i <= K; i++)
        ans = min(ans, dist[H][i]);

    if (ans == 1e18)
        ans = -1;

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Correct.
2 Correct 16 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1628 KB Correct.
2 Correct 22 ms 1884 KB Correct.
3 Correct 21 ms 1628 KB Correct.
4 Correct 22 ms 1836 KB Correct.
5 Correct 22 ms 1884 KB Correct.
6 Correct 22 ms 4756 KB Correct.
7 Correct 26 ms 4944 KB Correct.
8 Correct 13 ms 8024 KB Correct.
9 Correct 29 ms 1308 KB Correct.
10 Correct 21 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1704 KB Correct.
2 Correct 22 ms 1624 KB Correct.
3 Correct 22 ms 1628 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 23 ms 1368 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 29376 KB Correct.
2 Correct 247 ms 2228 KB Correct.
3 Correct 216 ms 2040 KB Correct.
4 Correct 228 ms 2060 KB Correct.
5 Correct 177 ms 1352 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1660 KB Correct.
2 Correct 21 ms 1880 KB Correct.
3 Correct 20 ms 1796 KB Correct.
4 Correct 21 ms 4444 KB Correct.
5 Correct 18 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1628 KB Correct.
2 Correct 18 ms 1624 KB Correct.
3 Correct 39 ms 29780 KB Correct.
4 Correct 20 ms 3420 KB Correct.
5 Correct 21 ms 1372 KB Correct.
6 Correct 21 ms 1784 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 2448 KB Correct.
2 Correct 34 ms 2448 KB Correct.
3 Correct 591 ms 31328 KB Correct.
4 Correct 458 ms 9936 KB Correct.
5 Correct 1132 ms 51612 KB Correct.
6 Correct 501 ms 42268 KB Correct.
7 Correct 433 ms 7600 KB Correct.
8 Correct 433 ms 3224 KB Correct.
9 Correct 215 ms 2276 KB Correct.
10 Correct 210 ms 2504 KB Correct.
11 Correct 413 ms 2828 KB Correct.
12 Correct 226 ms 2672 KB Correct.
13 Correct 237 ms 2588 KB Correct.
14 Correct 354 ms 11504 KB Correct.
15 Correct 415 ms 5436 KB Correct.
16 Correct 216 ms 2620 KB Correct.
17 Correct 266 ms 2584 KB Correct.
18 Correct 275 ms 2532 KB Correct.
19 Correct 629 ms 3584 KB Correct.
20 Correct 17 ms 840 KB Correct.
21 Correct 17 ms 1264 KB Correct.
22 Correct 30 ms 3532 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 5684 KB Correct.
2 Correct 142 ms 8236 KB Correct.
3 Correct 504 ms 82840 KB Correct.
4 Correct 1103 ms 8232 KB Correct.
5 Execution timed out 3046 ms 163484 KB Time limit exceeded
6 Halted 0 ms 0 KB -