Submission #756932

#	Time	Username	Problem	Language	Result	Execution time	Memory
756932		doowey	Cyberland (APIO23_cyberland)	C++17	97 / 100	656 ms	66404 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;
const int K = 65;
vector<pii> T[N];


bool can[N];
bool vv[N];
int A[N];
int ban;

void dfs(int u){
    vv[u]=true;
    if(u == 0 || A[u] == 0) can[u] = true;
    for(auto x : T[u]){
        if(!vv[x.fi] && x.fi != ban){
            dfs(x.fi);
        }
    }
}

double d[K][N];
double bins[K];
bool vis[K][N];

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    k = min(k, 60);
    bins[0] = 1.0;
    for(int i = 1; i <= k ; i ++ ){
        bins[i]=bins[i-1]*0.5;
    }
    ban = h;
    for(int i = 0 ; i < n; i ++ ){
        T[i].clear();
        can[i] = vv[i] = false;
        A[i] = arr[i];
    }
    for(int i = 0 ; i < m ; i ++ ){
        T[x[i]].push_back(mp(y[i], c[i]));
        T[y[i]].push_back(mp(x[i], c[i]));
    }
    dfs(0);
    double dis;
    double nw;
    double op = 1e18;
    bool fix = false;
    for(int j = 0 ; j <= k ; j ++ ){
        for(int i = 0 ; i < n; i ++ ){
            d[j][i] = 1e18;
            vis[j][i] = false;
        }
        priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
        if(j == 0){
            d[j][h] = 0.0;
            pq.push(mp(0.0, h));
        }
        else{
            for(int i = 0 ; i < n; i ++ ){
                if(vis[j - 1][i] && A[i] == 2){
                    for(auto x : T[i]){
                        if(x.fi == h) continue;
                        nw = x.se * bins[j];
                        if(d[j][x.fi] > d[j - 1][i] + nw){
                            d[j][x.fi] = d[j - 1][i] + nw;
                            pq.push(mp(d[j][x.fi], x.fi));
                        }
                    }
                }
            }
        }
        while(!pq.empty()){
            int node = pq.top().se;
            dis = pq.top().fi;
            pq.pop();
            if(vis[j][node]) continue;
            vis[j][node] = true;
            if(can[node]){
                op = min(op, dis);
                fix = true;
            }
            for(auto x : T[node]){
                if(x.fi == h) continue;
                nw = x.se * bins[j];
                if(dis + nw < d[j][x.fi]){
                    d[j][x.fi] = dis + nw;
                    pq.push(mp(d[j][x.fi], x.fi));
                }
            }
        }
    }
    if(fix)
        return op;
    return -1;
}

• 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