oj.uz

Submission #1065870

# Submission time Handle Problem Language Result Execution time Memory
1065870 2024-08-19T12:27:59 Z yanndev Cyberland (APIO23_cyberland) C++17
97 / 100
 1424 ms 69344 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, 63);

    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 16 ms 580 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 860 KB Correct.
2 Correct 22 ms 856 KB Correct.
3 Correct 39 ms 856 KB Correct.
4 Correct 39 ms 600 KB Correct.
5 Correct 21 ms 828 KB Correct.
6 Correct 23 ms 3996 KB Correct.
7 Correct 25 ms 4016 KB Correct.
8 Correct 22 ms 7516 KB Correct.
9 Correct 20 ms 344 KB Correct.
10 Correct 20 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 39 ms 820 KB Correct.
3 Correct 20 ms 856 KB Correct.
4 Correct 22 ms 544 KB Correct.
5 Correct 23 ms 548 KB Correct.
6 Correct 6 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 26516 KB Correct.
2 Correct 250 ms 1248 KB Correct.
3 Correct 217 ms 1244 KB Correct.
4 Correct 240 ms 1184 KB Correct.
5 Correct 176 ms 632 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 816 KB Correct.
2 Correct 21 ms 604 KB Correct.
3 Correct 35 ms 804 KB Correct.
4 Correct 20 ms 3932 KB Correct.
5 Correct 19 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 792 KB Correct.
2 Correct 19 ms 848 KB Correct.
3 Correct 51 ms 28040 KB Correct.
4 Correct 15 ms 2860 KB Correct.
5 Correct 21 ms 556 KB Correct.
6 Correct 23 ms 852 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 1580 KB Correct.
2 Correct 38 ms 2436 KB Correct.
3 Correct 641 ms 28960 KB Correct.
4 Correct 505 ms 7640 KB Correct.
5 Correct 1424 ms 49828 KB Correct.
6 Correct 539 ms 40872 KB Correct.
7 Correct 448 ms 7508 KB Correct.
8 Correct 435 ms 1840 KB Correct.
9 Correct 234 ms 2252 KB Correct.
10 Correct 211 ms 1536 KB Correct.
11 Correct 426 ms 976 KB Correct.
12 Correct 245 ms 1612 KB Correct.
13 Correct 259 ms 1620 KB Correct.
14 Correct 383 ms 10152 KB Correct.
15 Correct 431 ms 3452 KB Correct.
16 Correct 231 ms 1664 KB Correct.
17 Correct 272 ms 1536 KB Correct.
18 Correct 262 ms 1576 KB Correct.
19 Correct 680 ms 1652 KB Correct.
20 Correct 16 ms 840 KB Correct.
21 Correct 17 ms 1184 KB Correct.
22 Correct 38 ms 3264 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 4448 KB Correct.
2 Correct 106 ms 7848 KB Correct.
3 Incorrect 413 ms 69344 KB Wrong Answer.
4 Halted 0 ms 0 KB -