Submission #1194887

#TimeUsernameProblemLanguageResultExecution timeMemory
1194887ackhavaCyberland (APIO23_cyberland)C++20
0 / 100
3098 ms120648 KiB
#include "cyberland.h" #include <bits/stdc++.h> #pragma GCC optimize "O3,unroll-loops,trapv" #pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2" #define fi first #define se second #define pb push_back #define REP(i,o,n) for(auto i=o;i<n;i++) using namespace std; #define __int128 long long __int128 cost[200100][70]; vector<pair<int, __int128>> adj[200100]; vector<int> arr; vector<int> src; void dfs(int node, int H){ if(cost[node][0]!=-1)return; cost[node][0]=0; if(arr[node]==0)src.pb(node); if(src.size()&&src.back()==H)return; if(node==H)return; for(auto i:adj[node])dfs(i.fi,H); } 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) { for(auto&i:adj)i.clear(); memset(cost,-1,sizeof cost); ::arr=arr; src.clear(); REP(i,0,M){ adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]}); } src.pb(0); dfs(0,H); memset(cost,-1,sizeof cost); if(src.size() && src.back()==H)return 0; K = min(K,68); return src.size(); priority_queue<pair<__int128,pair<int,int>>,vector<pair<__int128,pair<int,int>>>,greater<pair<__int128,pair<int,int>>>> pq; for(auto i:src)pq.push({0,{i,0}}); while(pq.size()){ auto top=pq.top();pq.pop(); assert(top.fi>=0); if(top.se.se > K)continue; if(cost[top.se.fi][top.se.se]!=-1)continue; cost[top.se.fi][top.se.se]=top.fi; // cerr<<"POS "<<top.se.fi<<", JUMP "<<top.se.se<<": "<<(long long)top.fi<<endl; if(top.se.fi == H)continue; __int128 mul=1; mul<<=top.se.se; for(auto i:adj[top.se.fi]){ if(arr[i.fi]==2)pq.push({top.fi+mul*i.se,{i.fi,top.se.se+1}}); pq.push({top.fi+mul*i.se,{i.fi,top.se.se}}); } } long double ans=cost[H][0]; // assert(0); __int128 div=1; REP(i,0,K+1){ if(cost[H][i]!=-1)ans=(min(ans,((long double)cost[H][i])/div)); div*=2; } 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...