Submission #1228065

#TimeUsernameProblemLanguageResultExecution timeMemory
1228065DzadzoCyberland (APIO23_cyberland)C++20
0 / 100
305 ms23392 KiB
#include <bits/stdc++.h> #include "cyberland.h" #define ll long long #define pb push_back #define S second #define F first #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vp vector<pii> #define vvp vector<vp> #define vb vector<bool> #define vvb vector<vb> #define INF 1000000000000000 #define MOD 1000000007 #define MAXN 200000 using namespace std; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 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) { vvp adj(n); for (int i=0;i<m;i++) { adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]}); } vector <vector <double>> dist(n,vector <double>(31,INF)); dist[h][0]=0; set <pair <pair <double,int>,int>> st; st.insert({{dist[h][0],0},h}); while (st.size()) { int v=st.begin()->S; int k=st.begin()->F.S; st.erase(st.begin()); for (auto &[to,w]:adj[v]) { if (dist[to][k] > dist[v][k]+w ) { st.erase({{dist[to][k],k},to}); dist[to][k]=dist[v][k]+w; st.insert({{dist[to][k],k},to}); } if (arr[to]==2 && k!=30) { if (dist[to][k+1] > 2*(dist[v][k]+w) ) { st.erase({{dist[to][k+1],k+1},to}); dist[to][k+1]=2*(dist[v][k]+w); st.insert({{dist[to][k+1],k+1},to}); } } } } vb visited(n); bool res=false; function<void(int)> dfs = [&](int v) { // cout<<v<<'\n'; if (v==h) { res=true; return; } visited[v]=true; for (auto &[to,w]:adj[v]) { if (!visited[to]) { dfs(to); } } }; dfs(0); if (!res)return -1; double ans=INF; int z=1; for (int q=0;q<=min(K,30);q++)ans=min(ans,dist[0][q]/z),z*=2; for (int i=1;i<n;i++) { if (!arr[i] && visited[i]) { int t=1; for (int q=0;q<=min(30,K);q++)ans=min(ans,dist[i][q] / t ) , t*=2; // ans=min(ans,dp[i][0]); } } return ans; } // int main() { // int n,m,k,h; // cin>>n>>m>>k>>h; // vi arr; // for (int i=0;i<n;i++) { // int x; // cin>>x; // arr.pb(x); // } // vi X,Y,C; // for (int i=0;i<m;i++) { // int x,y,c; // cin>>x>>y>>c; // X.pb(x); // Y.pb(y); // C.pb(c); // } // cout<<solve(n,m,k,h,X,Y,C,arr); // // } /* 3 2 30 1 1 1 2 1 2 23211 0 1 9991 */
#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...