| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 918621 | djs100201 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 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<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =1e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
if(!y)return x;
return gcd(y,x%y);
}
vector<P>v[n_];
double dist[n_][31],pw[n_];
ll par[n_];
ll find(ll x){
if(par[x]<0)return x;
return par[x]=find(par[x]);
}
void merge(ll x,ll y){
x=find(x),y=find(y);
if(x==y)return;
par[x]=y;
}
double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> C, vector<int> arr) {
n=N,m=M,k=min(30,K);
for(int i=0;i<N;i++){
par[i]=-1;
for(int j=0;j<=k;j++)dist[i][j]=inf;
}
pw[0]=1;
for(int i=1;i<=k;i++)pw[i]=pw[i-1]*2;
for(int i=0;i<M;i++){
merge(U[i],V[i]);
v[U[i]].push_back({V[i],C[i]});
v[V[i]].push_back({U[i],C[i]});
}
priority_queue<pair<double,P>,vector<pair<double,P>>,greater<>>pq;
pq.push({0.0,{H,0}});
dist[H][0]=0.0;
double ans=inf;
while(pq.size()){
double a=pq.top().first;
b=pq.top().second.first,c=pq.top().second.second;
pq.pop();
//cout<<a<<' '<<b<<' '<<c<<endl;
if(dist[b][c]<a)continue;
if(b==0){
ans=min(ans,a);
continue;
}
for(auto nxt:v[b]){
double cost=a+nxt.second/pw[c];
if(arr[nxt.first]==0){
if(find(nxt.first)==find(0))ans=min(ans,cost);
}
else if(arr[nxt.first]==1 || c==k){
if(cost<dist[nxt.first][c]){
dist[nxt.first][c]=cost;
pq.push({cost,{nxt.first,c}});
}
}
else{
if(cost<dist[nxt.first][c+1]){
dist[nxt.first][c+1]=cost;
pq.push({cost,{nxt.first,c+1}});
}
}
}
}
if(ans>=inf-10)return -1;
else return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
#endif
//cin >> tc;
cout<<fixed;
cout.precision(13);
//cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
}