oj.uz

Submission #749678

# Submission time Handle Problem Language Result Execution time Memory
749678 2023-05-28T11:20:59 Z Sacharlemagne Cyberland (APIO23_cyberland) C++17
97 / 100
 835 ms 2097152 KB 
#include "cyberland.h"
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const double INF = 1e18;
ll h,k;

vector<int> zeroes;
typedef priority_queue<pair<double,pll>, vector<pair<double,pll> >, greater<> > pita;
pita other;
void dijkstra(vector<vector<double> > &dist, vector<vector<pll>> &adj, vi &arr) {
    vector<bool> visited(dist.size());
    pita pq;
    swap(pq,other);
    while (!pq.empty()) {
        double curDist = pq.top().first;
        pll p = pq.top().second;
        pq.pop();
        ll K = p.second, node = p.first;
        if (node == h) continue;
        if (visited[node]) continue;
        visited[node] = true;
        for (pll u : adj[p.first]) {
            if (dist[u.first][K] > (curDist+u.second)) {
                dist[u.first][K] = curDist+u.second;
                pq.push({curDist+u.second,{u.first,K}});
            }
            if (arr[u.first] == 2 && K < k) {
                if (dist[u.first][K+1] > (curDist+u.second)/2.) {
                    dist[u.first][K+1] = (curDist+u.second)/2.;
                    other.push({(curDist+u.second)/2.,{u.first,K+1}});
                }
            }
        }
    }
}

void dfs(int node, vector<bool> &visited, vector<vector<pll> > &adj, vi &arr) {
    if (visited[node]) return;
    visited[node] = true;
    if (arr[node] == 0) zeroes.push_back(node);
    for (pll u : adj[node]) {
        dfs(u.first,visited,adj,arr);
    }
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
    zeroes.clear();
    other = pita();
    other.push({0,{0,0}});

    h = H, k = K;
    vector<vector<pll> > 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<bool> visited(N, false);
    visited[H] = true;
    dfs(0,visited,adj,arr);
    for (int i : zeroes) {
        adj[0].push_back({i,0});
    }
    vector<vector<double> > dist(N,vector<double>(k+1,INF));
    dist[0][0] = 0;
    for (int i = 0; i<=K; ++i) {
        dijkstra(dist,adj,arr);
    }
    double res = *min_element(dist[h].begin(),dist[h].end());
    return res==INF?-1:res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 468 KB Correct.
2 Correct 33 ms 404 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 692 KB Correct.
2 Correct 34 ms 716 KB Correct.
3 Correct 30 ms 724 KB Correct.
4 Correct 39 ms 724 KB Correct.
5 Correct 35 ms 684 KB Correct.
6 Correct 32 ms 4156 KB Correct.
7 Correct 33 ms 3980 KB Correct.
8 Correct 22 ms 7912 KB Correct.
9 Correct 31 ms 432 KB Correct.
10 Correct 32 ms 388 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 712 KB Correct.
2 Correct 32 ms 760 KB Correct.
3 Correct 29 ms 800 KB Correct.
4 Correct 35 ms 408 KB Correct.
5 Correct 36 ms 412 KB Correct.
6 Correct 8 ms 3668 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 23804 KB Correct.
2 Correct 130 ms 792 KB Correct.
3 Correct 118 ms 796 KB Correct.
4 Correct 138 ms 772 KB Correct.
5 Correct 87 ms 464 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 712 KB Correct.
2 Correct 29 ms 696 KB Correct.
3 Correct 31 ms 708 KB Correct.
4 Correct 29 ms 4020 KB Correct.
5 Correct 25 ms 416 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 740 KB Correct.
2 Correct 24 ms 716 KB Correct.
3 Correct 51 ms 29308 KB Correct.
4 Correct 18 ms 3028 KB Correct.
5 Correct 30 ms 404 KB Correct.
6 Correct 28 ms 832 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 716 KB Correct.
2 Correct 24 ms 852 KB Correct.
3 Correct 835 ms 28428 KB Correct.
4 Correct 333 ms 7288 KB Correct.
5 Correct 801 ms 21292 KB Correct.
6 Correct 283 ms 10592 KB Correct.
7 Correct 336 ms 7152 KB Correct.
8 Correct 262 ms 1508 KB Correct.
9 Correct 124 ms 752 KB Correct.
10 Correct 125 ms 740 KB Correct.
11 Correct 228 ms 796 KB Correct.
12 Correct 145 ms 772 KB Correct.
13 Correct 141 ms 788 KB Correct.
14 Correct 367 ms 10184 KB Correct.
15 Correct 284 ms 2796 KB Correct.
16 Correct 150 ms 788 KB Correct.
17 Correct 155 ms 796 KB Correct.
18 Correct 148 ms 724 KB Correct.
19 Correct 399 ms 756 KB Correct.
20 Correct 9 ms 340 KB Correct.
21 Correct 10 ms 612 KB Correct.
22 Correct 18 ms 1236 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 789 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -