# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
847648 | KN200711 | Cyberland (APIO23_cyberland) | C++17 | 94 ms | 23648 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cyberland.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
bool vis[100001];
vector< pair<int, int> > edge[100001];
void dfs(int a) {
vis[a] = 1;
for(auto p : edge[a]) {
if(!vis[p.fi]) dfs(p.fi);
}
}
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, 70);
for(int i=0;i<N;i++) {
vis[i] = 0;
edge[i].clear();
}
for(int i=0;i<x.size();i++) {
edge[x[i]].push_back(make_pair(y[i], c[i]));
edge[y[i]].push_back(make_pair(x[i], c[i]));
}
dfs(0);
vector< vector<double> > dp;
dp.resize(K + 1);
for(int i=0;i<=K;i++) {
dp[i].resize(N);
for(int c=0;c<N;c++) dp[i][c] = -1;
}
priority_queue< pair<double, pair<int, int> > > PQ;
for(int d=0;d<N;d++) {
if(d == 0 || (arr[d] == 0 && vis[d])) PQ.push(make_pair(0, make_pair(0, d)));
}
while(!PQ.empty()) {
double a = PQ.top().fi;
int nm = PQ.top().se.fi, pos = PQ.top().se.se;
PQ.pop();
if(nm > K) continue;
if(dp[nm][pos] != -1) continue;
dp[nm][pos] = -a;
// cout<<nm<<" "<<pos<<" "<<a<<endl;
if(pos == H) break;
for(auto p : edge[pos]) {
if(arr[p.fi] == 0) continue;
else if(arr[p.fi] == 1 && dp[nm][p.fi] == -1) PQ.push(make_pair(a - ((double) p.se), make_pair(nm, p.fi)));
else if(arr[p.fi] == 2) {
if(nm + 1 <= K && dp[nm+1][pos] == -1)PQ.push(make_pair((a - (double) p.se) / ((double) 2), make_pair(nm + 1, p.fi)));
if(dp[nm][pos] == -1) PQ.push(make_pair((a - (double) p.se), make_pair(nm + 1, p.fi)));
}
}
}
double ans = 1e18;
for(int v=0;v<=K;v++) {
if(dp[v][H] != -1) ans = min(ans, dp[v][H]);
}
if(ans == 1e18) ans = -1;
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |