oj.uz

Submission #845085

# Submission time Handle Problem Language Result Execution time Memory
845085 2023-09-06T11:53:41 Z veehj Cyberland (APIO23_cyberland) C++17
0 / 100
 3000 ms 17092 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 9296 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 17092 KB Time limit exceeded
2 Halted 0 ms 0 KB -