Submission #749678

#	Time	Username	Problem	Language	Result	Execution time	Memory
749678		Sacharlemagne	Cyberland (APIO23_cyberland)	C++17	97 / 100	835 ms	2097152 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3