Submission #756815

#	Time	Username	Problem	Language	Result	Execution time	Memory
756815		doowey	Cyberland (APIO23_cyberland)	C++17	8 / 100	36 ms	8900 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];

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]){
            dfs(x.fi);
        }
    }
}

double d[N];
bool vis[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);
    for(int i = 0 ; i < n; i ++ ){
        T[i].clear();
        can[i] = vv[i] = false;
        A[i] = arr[i];
        d[i] = 1e18;
        vis[i] = false;
    }
    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 sol = 1e18;
    priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
    d[h] = 0.0;
    pq.push(mp(0.0, h));
    int node;
    double res;
    while(!pq.empty()){
        node = pq.top().se;
        res = pq.top().fi;
        pq.pop();
        if(vis[node]) continue;
        if(can[node]) sol = min(sol, res);
        for(auto x : T[node]){
            if(d[x.fi] > d[node] + x.se){
                d[x.fi] = d[node] + x.se;
                pq.push(mp(d[x.fi], x.fi));
            }
        }
    }
    return sol;
}

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