oj.uz

Submission #876391

# Submission time Handle Problem Language Result Execution time Memory
876391 2023-11-21T16:27:31 Z hmm789 Cyberland (APIO23_cyberland) C++17
15 / 100
 647 ms 31224 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> adj[100000];
bool v[100000];
void dfs(int x) {
    v[x] = 1;
    for(auto i : adj[x]) if(!v[i.first]) dfs(i.first);
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K = min(K, 66);
    int cur, num;
    double d, ans = -1;
    for(int i = 0; i < N; i++) adj[i].clear();
    for(int i = 0; i < N; i++) v[i] = 0;
    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]});
    }
    double dist[N][K+1];
    for(int i = 0; i < N; i++) for(int j = 0; j <= K; j++) dist[i][j] = -1;
    dist[0][0] = 0;
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
    pq.push({0, 0, 0});
    dfs(0);
    for(int i = 0; i < N; i++) if(arr[i] == 0 && v[i]) {
        dist[i][0] = 0;
        pq.push({0, i, 0});
    }
    while(!pq.empty()) {
        tie(d, cur, num) = pq.top();
        pq.pop();
        if(dist[cur][num] != d) continue;
        if(cur == H) continue;
        for(auto i : adj[cur]) {
            double nd = d+i.second;
            if(arr[i.first] == 0) nd = 0;
            if(dist[i.first][num] == -1 || dist[i.first][num] > nd) {
                dist[i.first][num] = nd;
                pq.push({nd, i.first, num});
            }
            if(arr[i.first] == 2) {
                if(num+1 > K) continue;
                nd /= 2.0;
                if(dist[i.first][num+1] == -1 || dist[i.first][num+1] > nd) {
                    dist[i.first][num+1] = nd;
                    pq.push({nd, i.first, num+1});
                }
            }
        }
    }
    for(int i = 0; i <= K; i++) {
        if(dist[H][i] != -1) {
            if(ans == -1) ans = dist[H][i];
            else ans = min(ans, dist[H][i]);
        }
    }
    return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2904 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3164 KB Correct.
2 Correct 22 ms 3088 KB Correct.
3 Correct 20 ms 3164 KB Correct.
4 Correct 21 ms 3164 KB Correct.
5 Correct 22 ms 3164 KB Correct.
6 Correct 20 ms 5724 KB Correct.
7 Correct 26 ms 5724 KB Correct.
8 Correct 19 ms 8948 KB Correct.
9 Correct 20 ms 2652 KB Correct.
10 Correct 20 ms 2884 KB Correct.

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3164 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 647 ms 31224 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3164 KB Correct.
2 Correct 20 ms 3164 KB Correct.
3 Correct 20 ms 3320 KB Correct.
4 Correct 21 ms 6132 KB Correct.
5 Correct 18 ms 2652 KB Correct.

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3160 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 3596 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 551 ms 5032 KB Wrong Answer.
2 Halted 0 ms 0 KB -