Submission #1191848

#TimeUsernameProblemLanguageResultExecution timeMemory
1191848MalixCyberland (APIO23_cyberland)C++17
63 / 100
3095 ms34156 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,ll,ll> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int n,m,h; vector<vector<pi>> a; vi b; double dist[100000][31]; void dfs(int x){ b[x]=1; if(x==h)return; for(auto u:a[x])if(b[u.F]==0)dfs(u.F); } 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;h=H; a.clear();a.resize(n); REP(i,0,m){ a[X[i]].PB({Y[i],C[i]}); a[Y[i]].PB({X[i],C[i]}); } b.clear();b.resize(n,0); dfs(0); if(b[H]==0)return -1; REP(i,0,100000)REP(j,0,k+1)dist[i][j]=1e14+10; priority_queue<tuple<double,int,int>> pq; dist[H][0]=0; pq.push({0,H,0}); while(!pq.empty()){ double x=-get<0>(pq.top()); int y=get<1>(pq.top()); int z=get<2>(pq.top()); pq.pop(); if(dist[y][z]<x)continue; for(auto u:a[y])if(u.F!=H){ if(arr[u.F]==2&&dist[u.F][min(z+1,30)]>x+(double)(u.S)/(1<<z)){ dist[u.F][min(z+1,30)]=x+(double)(u.S)/(1<<z); pq.push({-dist[u.F][min(z+1,30)],u.F,min(z+1,30)}); } else if(dist[u.F][z]>x+(double)(u.S)/(1<<z)){ dist[u.F][z]=x+(double)(u.S)/(1<<z); pq.push({-dist[u.F][z],u.F,z}); } } } double ans=1e14+10; REP(i,0,n)if(b[i]&&arr[i]==0)REP(j,0,k+1)ans=min(ans,dist[i][j]); REP(j,0,k+1)ans=min(ans,dist[0][j]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...