oj.uz

Submission #1065881

# Submission time Handle Problem Language Result Execution time Memory
1065881 2024-08-19T12:30:09 Z yanndev Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 158272 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, 66);

    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 15 ms 604 KB Correct.
2 Correct 15 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 860 KB Correct.
2 Correct 21 ms 860 KB Correct.
3 Correct 20 ms 820 KB Correct.
4 Correct 21 ms 604 KB Correct.
5 Correct 21 ms 820 KB Correct.
6 Correct 19 ms 4000 KB Correct.
7 Correct 24 ms 4016 KB Correct.
8 Correct 13 ms 7652 KB Correct.
9 Correct 20 ms 348 KB Correct.
10 Correct 22 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 604 KB Correct.
2 Correct 22 ms 836 KB Correct.
3 Correct 25 ms 856 KB Correct.
4 Correct 31 ms 528 KB Correct.
5 Correct 22 ms 344 KB Correct.
6 Correct 5 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 26920 KB Correct.
2 Correct 249 ms 1236 KB Correct.
3 Correct 212 ms 1264 KB Correct.
4 Correct 225 ms 1088 KB Correct.
5 Correct 175 ms 596 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 816 KB Correct.
2 Correct 20 ms 860 KB Correct.
3 Correct 21 ms 840 KB Correct.
4 Correct 20 ms 3932 KB Correct.
5 Correct 18 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 17 ms 860 KB Correct.
3 Correct 49 ms 28084 KB Correct.
4 Correct 13 ms 2868 KB Correct.
5 Correct 20 ms 524 KB Correct.
6 Correct 21 ms 812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 1472 KB Correct.
2 Correct 33 ms 2372 KB Correct.
3 Correct 594 ms 28764 KB Correct.
4 Correct 464 ms 7492 KB Correct.
5 Correct 1126 ms 49828 KB Correct.
6 Correct 489 ms 40872 KB Correct.
7 Correct 428 ms 7592 KB Correct.
8 Correct 425 ms 1672 KB Correct.
9 Correct 210 ms 2216 KB Correct.
10 Correct 210 ms 1540 KB Correct.
11 Correct 413 ms 1148 KB Correct.
12 Correct 222 ms 1608 KB Correct.
13 Correct 241 ms 1636 KB Correct.
14 Correct 361 ms 9964 KB Correct.
15 Correct 416 ms 3392 KB Correct.
16 Correct 212 ms 1548 KB Correct.
17 Correct 260 ms 1620 KB Correct.
18 Correct 257 ms 1532 KB Correct.
19 Correct 628 ms 1644 KB Correct.
20 Correct 16 ms 840 KB Correct.
21 Correct 17 ms 1180 KB Correct.
22 Correct 29 ms 3220 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 4576 KB Correct.
2 Correct 112 ms 8200 KB Correct.
3 Correct 392 ms 70736 KB Correct.
4 Correct 949 ms 4736 KB Correct.
5 Execution timed out 3044 ms 158272 KB Time limit exceeded
6 Halted 0 ms 0 KB -