Submission #845085

#	Time	Username	Problem	Language	Result	Execution time	Memory
845085		veehj	Cyberland (APIO23_cyberland)	C++17	0 / 100	3045 ms	17092 KiB

cyberland

#include "cyberland.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
vector<bool> zero;
vector<double> kk;
vector<double> val;
vector<vector<pair<int, int>>> adj;
vector<int> a;
int k; double ans=-1;

void setkk(int x){
    if(x>k) return;
    kk.pb(kk.back()/2);
    setkk(x+1);
}

void go(int nw, double curr, int used){
    if(val[nw]==-1) val[nw]=curr;
    else if(val[nw]<=curr) return;
    val[nw]=min(val[nw], curr);
    if(a[nw]==0 || nw==0){
        zero[nw]=1;
        return;
    }
    if(a[nw]==2 && used<k) used++;
    for(auto& u : adj[nw]){
        go(u.F, curr+u.S*kk[used], used);
    }
}

vector<bool> vist;

void find(int x){
    vist[x]=1;
    if(x!=0 && zero[x] && val[x]!=-1){
        if(ans==-1) ans=val[x];
        else ans=min(val[x], ans);
    }
    for(auto& u : adj[x]){
        if(vist[u.F]) continue;
        find(u.F);
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    a=arr; k=K;
    vist.assign(N, 0);
    kk.pb(1);
    setkk(0);
    zero.assign(N, 0);
    val.assign(N, -1);
    adj.resize(N);
    for(int i=0; i<M; i++){
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    go(H, 0, 0);
    ans=val[0];
    find(0);
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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