Submission #876399

#	Time	Username	Problem	Language	Result	Execution time	Memory
876399		hmm789	Cyberland (APIO23_cyberland)	C++17	68 / 100	572 ms	64852 KiB

cyberland

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

vector<pair<int, int>> adj[100000];
bool v[100000];
int h;
void dfs(int x) {
    v[x] = 1;
    for(auto i : adj[x]) if(!v[i.first] && i.first != h) dfs(i.first);
}
 
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, 66);
    h = H;
    int cur, num;
    double d, ans = -1;
    for(int i = 0; i < N; i++) adj[i].clear();
    for(int i = 0; i < N; i++) v[i] = 0;
    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]});
    }
    double dist[N][K+1];
    for(int i = 0; i < N; i++) for(int j = 0; j <= K; j++) dist[i][j] = -1;
    dist[0][0] = 0;
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
    pq.push({0, 0, 0});
    dfs(0);
    for(int i = 0; i < N; i++) if(arr[i] == 0 && v[i]) {
        dist[i][0] = 0;
        pq.push({0, i, 0});
    }
    bool ok[K+1];
    int cnt = 0;
    memset(ok, 0, sizeof(ok));
    while(!pq.empty()) {
        tie(d, cur, num) = pq.top();
        pq.pop();
        if(dist[cur][num] != d) continue;
        if(cur == H) {
            if(!ok[num]) cnt++;
            ok[num] = 1;
            if(cnt == K+1) goto ed;
            continue;
        }
        for(auto i : adj[cur]) {
            double nd = d+i.second;
            if(arr[i.first] == 0) nd = 0;
            if(dist[i.first][num] == -1 || dist[i.first][num] > nd) {
                dist[i.first][num] = nd;
                pq.push({nd, i.first, num});
            }
            if(arr[i.first] == 2) {
                if(num+1 > K) continue;
                nd /= 2.0;
                if(dist[i.first][num+1] == -1 || dist[i.first][num+1] > nd) {
                    dist[i.first][num+1] = nd;
                    pq.push({nd, i.first, num+1});
                }
            }
        }
    }
    ed:;
    for(int i = 0; i <= K; i++) {
        if(dist[H][i] != -1) {
            if(ans == -1) ans = dist[H][i];
            else ans = min(ans, dist[H][i]);
        }
    }
    return ans;
}

• 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: 0 / 29
• Subtask 8: 0 / 3