# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
879135 | leanchec | Cyberland (APIO23_cyberland) | C++17 | 3057 ms | 82432 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>
using namespace std;
vector<pair<int,int>> adj[100100];
bool visited[100100]={};
void dfs(int cur, int H){
visited[cur]=true;
for(int i=0; i<(int)adj[cur].size(); i++){
int viz=adj[cur][i].first;
if(visited[viz] || viz==H)continue;
dfs(viz, H);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr){
for(int i=0; i<N; i++){
adj[i].clear();
visited[i]=0;
}
for(int i=0; i<M; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
dfs(0, H);
double dist[100100][75], po[74];
bool achou[100100][75];
po[0]=1;
for(int i=1; i<=69; i++)po[i]=po[i-1]*2;
for(int i=0; i<N; i++){
for(int j=0; j<=min(K, 70); j++){
dist[i][j]=1e15;
achou[i][j]=false;
}
}
set<array<double, 3>> ss;
ss.insert({0, H, 0});
dist[H][0]=0;
while(!ss.empty()){
array<double, 3> curtop=*ss.begin();
ss.erase(ss.begin());
int cur=curtop[1];
int curk=curtop[2];
if(cur==0 || arr[cur]==0 || curk==70){
return dist[cur][curk];
}
if(achou[cur][curk])continue;
achou[cur][curk]=true;
for(int i=0; i<(int)adj[cur].size(); i++){
int viz=adj[cur][i].first;
if(!visited[viz])continue;
double w=adj[cur][i].second;
if(arr[cur]==2 && curk+1<=K){
if(dist[viz][curk+1]>dist[cur][curk]+w/po[curk+1]){
ss.erase({dist[viz][curk+1], viz, curk+1});
dist[viz][curk+1]=dist[cur][curk]+w/po[curk+1];
ss.insert({dist[viz][curk+1], viz, curk+1});
}
}
else if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){
ss.erase({dist[viz][curk], viz, curk});
dist[viz][curk]=dist[cur][curk]+w/po[curk];
ss.insert({dist[viz][curk], viz, curk});
}
}
}
return -1;
}
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... |