oj.uz

Submission #749675

# Submission time Handle Problem Language Result Execution time Memory
749675 2023-05-28T11:19:12 Z Sacharlemagne Cyberland (APIO23_cyberland) C++17
0 / 100
 1000 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(),false);
    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);
    }
    int res = *min_element(dist[h].begin(),dist[h].end());
    return res==INF?-1:res;
}

/**
* 1
3 3 69 2
1 2 1
0 1 1
0 2 2
1 2 1


 1
3 2 2
2
1 2 1
0 1 3
1 2 2

5 4 69 4
1 1 0 1 1
0 1 10
0 2 2
2 3 1
2 4 1

 6 5 69 1
1 1 0 1 0 1
0 1 2
1 2 1
1 3 5
3 4 69
3 5 2

 3 4 60 1
 1 1 1
0 1 6
0 2 2
2 1 3
0 2 4

 8 8 69 6
1 1 1 0 1 1 1 0
0 1 1
0 2 1
1 4 1
2 3 1
2 5 1
4 6 1
5 6 1
6 7 1

 6 5 5 5
 1 0 2 2 2 1
0 1 4
1 2 8
2 3 8
3 4 8
4 5 0

 10
3 2 30 2
1 2 1
1 2 12
2 0 4
 4 4 30 3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 468 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 724 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 760 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 23696 KB Correct.
2 Incorrect 132 ms 852 KB Double -2.14748e+09 violates the range [-1, 1e+18]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 732 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 728 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 744 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

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