Submission #983933

#	Time	Username	Problem	Language	Result	Execution time	Memory
983933		Shayan86	Cyberland (APIO23_cyberland)	C++17	15 / 100	938 ms	82836 KiB

cyberland

//#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll K = 72;
const ll N = 1e5 + 50;
const ll inf = 1e18;

ll n, m, k, H, a[N];
ld dist[N][K];

bool mark[N];
vector<pll> adj[N];

void dfs(int v){
    mark[v] = true;
    for(auto [u, w]: adj[v]) if(!mark[u]) dfs(u);
}

void dijk(){
    for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;

    priority_queue<pair<pair<int, ld>, int>, vector<pair<pair<int, ld>, int>>, greater<pair<pair<int, ld>, int>>> pq;
    for(int i = 0; i < n; i++) if(!a[i] && mark[i]){
        dist[i][0] = 0; pq.push({{0, dist[i][0]}, i});
    }

    while (!pq.empty()){
        auto [id, vd] = pq.top().F;
        auto v = pq.top().S;
        pq.pop();

        if(id < k){
            if(dist[v][id+1] > dist[v][id]){
                dist[v][id+1] = dist[v][id];
                pq.push({{id+1, dist[v][id+1]}, v});
            }
        }

        if(v == H) continue;

        for (auto [u, w]: adj[v]){
            if(dist[u][id] > dist[v][id] + w){
                dist[u][id] = dist[v][id] + w;
                pq.push({{id, dist[u][id]}, u});
            }
            if(a[u] != 2 || id == k) continue;
            if(dist[u][id+1] * 2 > dist[v][id] + w){
                dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
                pq.push({{id+1, dist[u][id+1]}, u});
            }
        }
    }
}

void dijk2(){
    for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;

    priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> pq;
    for(int i = 0; i < n; i++) if(i != H && mark[i]){
        dist[i][0] = 0; pq.push({dist[i][0], {i, 0}});
    }

    while (!pq.empty()){
        auto [v, id] = pq.top().S;
        auto vd = pq.top().F;
        pq.pop();

        if(vd != dist[v][id]) continue;

        if(v == H) continue;

        for (auto [u, w]: adj[v]){
            if(dist[u][id] > dist[v][id] + w){
                dist[u][id] = dist[v][id] + w;
                pq.push({dist[u][id], {u, id}});
            }
            if(a[u] != 2 || id == k) continue;
            if(dist[u][id+1] * 2 > dist[v][id] + w){
                dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
                pq.push({dist[u][id+1], {u, id+1}});
            }
        }
    }
}

double solve(int N, int M, int Kk, int H_, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    n = N; m = M; k = Kk; H = H_;

    for(int i = 0; i < n; i++){
        adj[i].clear(); mark[i] = false;
    }

    for(int i = 0; i < m; i++){
        int u = x[i];
        int v = y[i];
        int w = c[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    for(int i = 0; i < n; i++) a[i] = arr[i];

    dfs(0);
    if(!mark[H]) return -1;

    k = min(k, 70ll);
    a[0] = 0; dijk();

    ld res = dist[H][k];
/*
    if(Kk > k){
        k++; dijk2();
        res = min(res, dist[H][k]);
    }
*/

    if(res >= inf) return -1;
    return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3