Submission #1292883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292883		goulthen	Cyberland (APIO23_cyberland)	C++20	15 / 100	39 ms	14512 KiB

cyberland

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

using namespace std;

#define ld long double
#define pii pair<ld,int>
#define ll long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
const ll INF = 1e18+10;
const int MAXN = 1e5+10;
bool mk[MAXN];

void dfs(int u, vector<vector<pii>> &g) {
    if(mk[u]) return;
    mk[u] = 1;
    for(auto &[v,w] : g[u]) dfs(v,g);
}

void dijkstra(priority_queue<pii,vector<pii>,greater<pii>> &pq, vector<ld> &dist, vector<vector<pii>> &g, int N) {
    vector<bool> vis(N, 0LL);

    while (!pq.empty()) {
        auto [d,u] = pq.top();pq.pop();
        if(vis[u]) continue;
        //cout << u << ' ' << d << ' ' << ck << '\n';
        vis[u] = 1;

        for(auto &[v,w] : g[u]) {
            if (d+w >= dist[v]) continue;

            dist[v] = d+w;
            pq.push({dist[v],v});
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K=min(K,100);
    rep(i,0,N-1) mk[i] = 0;
    vector<ld> dist(N, INF);
    vector<vector<pii>> g(N);

    rep(i,0,M-1) {
        g[x[i]].emplace_back(y[i],c[i]);
        g[y[i]].emplace_back(x[i],c[i]);
    }
    dfs(0,g);
 
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    dist[0] = 0;
    pq.push({0,0});
    rep(i,1,N-1) if(arr[i]==0 && mk[i]) {
        pq.push({0,i});
        dist[i] = 0;
    }

    dijkstra(pq,dist,g,N);
    vector<ld> dist2(N,INF);
    dist2[H] = 0;
    pq.push({0,H});
    dijkstra(pq, dist2, g, N);

    if(!mk[H]) return -1;

    ld ans = INF;
    rep(i,0,N-1) {
        if(!mk[i]) continue;

        int mn = 1e9+10;
        for(auto &[v,w] : g[i]) {
            if(v!=H) mn = min(mn,w);
        }
        ld d = dist[i];
        if(arr[i] == 2) d /= 2;
        //cout << d << ' ' << dist[i] << '\n';
        rep(j,2,K) {
            if(arr[i] != 2) break;
            if(d+2*mn >= 2*d) break;
            d = d/2+mn;
        }
        //cout << d << ' ' << dist2[i] << '\n';
        ans = min(ans, d+dist2[i]);
    }

    if(ans == INF) return -1;
    return ans;
}

• 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