Submission #981847

#	Time	Username	Problem	Language	Result	Execution time	Memory
981847		FZ_Melo	Cyberland (APIO23_cyberland)	C++17	8 / 100	3036 ms	2097152 KiB

cyberland

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

struct ari{
    int node;
    double cnt;
};

vector<vector<ari>> adj;
int state[100000];
int n, m, k, fin;
double ans;

void dfs(int node, double cnt, int ant, int left){
    if(node==fin){
        if(ans==(1<<30))
            ans=cnt;
        else
            ans=min(ans, cnt);
        return;
    }
    
    for(auto h: adj[node]){
        if(h.node==ant)
            continue;
        if(state[node]==0)
            dfs(h.node, h.cnt, node, left-1);
        dfs(h.node, cnt+h.cnt, node, left);
    }
}

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) {
    
    n=N; m=M; k=K; fin=H;
    adj.clear();
    adj.resize(n);
    ans=(1<<30);
    for(int i=0; i<m; i++){
        adj[x[i]].push_back({y[i], (double)c[i]});
        adj[y[i]].push_back({x[i], (double)c[i]});
    }
    for(int i=0; i<n; i++)
        state[i]=arr[i];
    dfs(0, 0, 0, k);
    return ans;
}

• 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