Submission #1292572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292572		Hamed_Ghaffari	Cyberland (APIO23_cyberland)	C++20	100 / 100	1267 ms	17460 KiB

cyberland

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

using pii = pair<int, int>;

#define X first
#define Y second
#define mins(a, b) (a = min(a, b))

const int MXN = 1e5+5;
const double inf = 1e16;

int h;
vector<pii> g[MXN];
double dis[MXN], dis2[MXN];
bool vis[MXN];

void dfs(int v) {
    vis[v] = 1;
    for(auto [u, w] : g[v])
        if(!vis[u] && u!=h)
            dfs(u);
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    ::h = h;
    for(int i=0; i<n; i++) {
        dis[i] = i ? inf : 0;
        g[i].clear();
        vis[i] = 0;
    }
    for(int i=0; i<m; i++) {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    dfs(0);
    for(int i=0; i<n; i++)
        if(vis[i] && !arr[i])
            dis[i] = 0;
    double ans = inf;
    for(int x=min(70, k); x>=0; x--) {
        priority_queue<pair<double, int>> pq;
        for(int i=0; i<n; i++) vis[i] = 0, pq.push({-dis[i], i});
        while(!pq.empty()) {
            double d = -pq.top().X;
            int v = pq.top().Y;
            pq.pop();
            if(vis[v]) continue;
            vis[v] = 1;
            for(auto [u, w] : g[v])
                if(u!=h && dis[u] > dis[v]+w)
                    pq.push({-(dis[u] = dis[v]+w), u});
        }
        for(int v=0; v<n; v++) {
            dis2[v] = inf;
            for(auto [u, w] : g[v])
                if(arr[u]==2 && dis[u] < inf/2)
                    mins(dis2[v], dis[u] / 2 + w);
        }
        double res = x ? dis2[h] : inf;
        for(auto [u, w] : g[h]) mins(res, dis[u]+w);
        for(int i=0; i<n; i++) dis[i] = i==h ? inf : dis2[i];
        mins(ans, res);
    }
    return ans < inf/2 ? ans : -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: 3 / 3