oj.uz

답안 #985360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985360 2024-05-17T16:43:46 Z CrazyBotBoy 사이버랜드 (APIO23_cyberland) C++17
15 / 100
 382 ms 20572 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;

const int MAXN = 100005;

struct disj {
    int pa[MAXN];
    void init(int n) { iota(pa, pa + n + 1, 0); }
    int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
    bool uni(int p, int q) {
        p = find(p);
        q = find(q);
        if (p == q)
            return 0;
        pa[q] = p;
        return 1;
    }
} disj;

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, 69);  // Limiting K to a reasonable value to handle large inputs
    vector<vector<pi>> gph(N);
    disj.init(N);
    for (int i = 0; i < M; i++) {
        if (x[i] != H && y[i] != H)
            disj.uni(x[i], y[i]);
        gph[x[i]].push_back({c[i], y[i]});
        gph[y[i]].push_back({c[i], x[i]});
    }

    vector<double> pwr(K + 1, 1);
    for (int i = 1; i <= K; i++)
        pwr[i] = pwr[i - 1] / 2;

    arr[0] = 0;  // Ensuring starting point has no special ability
    vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
    using node = tuple<double, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;

    auto enq = [&](int k, int x, double d) {
        if (dist[k][x] > d) {
            dist[k][x] = d;
            pq.push({d, k, x});
        }
    };

    enq(K, 0, 0);  // Start from country 0 with full divide-by-2 abilities

    while (!pq.empty()) {
        auto [d, k, v] = pq.top();
        pq.pop();
        if (dist[k][v] < d)
            continue;
        if (v == H)
            return d;  // Return the distance once Cyberland is reached
        for (auto &[cost, w] : gph[v]) {
            enq(k, w, d + cost);
            if (arr[w] == 2 && k > 0) {
                enq(k - 1, w, d + cost * pwr[K - k + 1]);
            } else if (arr[w] == 0) {
                enq(k, w, 0);  // If the country's ability sets time to 0
            }
        }
    }
    return -1;  // If Cyberland is not reachable
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 856 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1708 KB Correct.
2 Correct 25 ms 1820 KB Correct.
3 Correct 24 ms 1852 KB Correct.
4 Correct 25 ms 1816 KB Correct.
5 Correct 24 ms 1792 KB Correct.
6 Correct 20 ms 4684 KB Correct.
7 Correct 28 ms 4392 KB Correct.
8 Correct 14 ms 7772 KB Correct.
9 Correct 30 ms 1368 KB Correct.
10 Correct 23 ms 1372 KB Correct.

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 1760 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 20572 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1664 KB Correct.
2 Correct 24 ms 1860 KB Correct.
3 Correct 30 ms 1868 KB Correct.
4 Correct 22 ms 4132 KB Correct.
5 Correct 21 ms 1368 KB Correct.

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 1816 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 173 ms 2392 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 3468 KB Wrong Answer.
2 Halted 0 ms 0 KB -