oj.uz

Submission #1065875

# Submission time Handle Problem Language Result Execution time Memory
1065875 2024-08-19T12:28:37 Z yanndev Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 159548 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, 70);

    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 25 ms 572 KB Correct.
2 Correct 16 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Correct.
2 Correct 21 ms 836 KB Correct.
3 Correct 22 ms 816 KB Correct.
4 Correct 31 ms 836 KB Correct.
5 Correct 21 ms 860 KB Correct.
6 Correct 19 ms 3872 KB Correct.
7 Correct 26 ms 3852 KB Correct.
8 Correct 15 ms 7516 KB Correct.
9 Correct 33 ms 344 KB Correct.
10 Correct 21 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 604 KB Correct.
2 Correct 35 ms 860 KB Correct.
3 Correct 21 ms 856 KB Correct.
4 Correct 23 ms 552 KB Correct.
5 Correct 22 ms 348 KB Correct.
6 Correct 9 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 28260 KB Correct.
2 Correct 259 ms 1232 KB Correct.
3 Correct 217 ms 1288 KB Correct.
4 Correct 245 ms 1112 KB Correct.
5 Correct 178 ms 612 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 820 KB Correct.
2 Correct 22 ms 836 KB Correct.
3 Correct 21 ms 864 KB Correct.
4 Correct 25 ms 3928 KB Correct.
5 Correct 20 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 860 KB Correct.
2 Correct 17 ms 844 KB Correct.
3 Correct 61 ms 27988 KB Correct.
4 Correct 15 ms 2652 KB Correct.
5 Correct 20 ms 552 KB Correct.
6 Correct 21 ms 808 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 1476 KB Correct.
2 Correct 42 ms 2448 KB Correct.
3 Correct 624 ms 28836 KB Correct.
4 Correct 504 ms 7644 KB Correct.
5 Correct 1400 ms 49840 KB Correct.
6 Correct 573 ms 40872 KB Correct.
7 Correct 432 ms 7592 KB Correct.
8 Correct 436 ms 1620 KB Correct.
9 Correct 211 ms 1996 KB Correct.
10 Correct 214 ms 1612 KB Correct.
11 Correct 437 ms 972 KB Correct.
12 Correct 227 ms 1648 KB Correct.
13 Correct 247 ms 1664 KB Correct.
14 Correct 363 ms 9964 KB Correct.
15 Correct 417 ms 3388 KB Correct.
16 Correct 217 ms 1612 KB Correct.
17 Correct 264 ms 1556 KB Correct.
18 Correct 256 ms 1516 KB Correct.
19 Correct 636 ms 1596 KB Correct.
20 Correct 17 ms 728 KB Correct.
21 Correct 17 ms 1060 KB Correct.
22 Correct 31 ms 3280 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 4436 KB Correct.
2 Correct 126 ms 8760 KB Correct.
3 Correct 461 ms 74060 KB Correct.
4 Correct 1032 ms 4976 KB Correct.
5 Execution timed out 3056 ms 159548 KB Time limit exceeded
6 Halted 0 ms 0 KB -