Submission #756130

#TimeUsernameProblemLanguageResultExecution timeMemory
756130HaciyevAlikCyberland (APIO23_cyberland)C++17
44 / 100
936 ms8800 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second const int mx=1e5+5; int n,m,h,k,used[mx],used2[15]; long dis[mx]; vector<pair<int,int>> g[mx]; struct triple { int u,v,w; }; bool comp(triple a,triple b) { if(a.u < b.u) { return 0; } return 1; } void dfs(int u) { used[u]=1; for(int i=0;i<int(g[u].size());++i) { int v=g[u][i].ff; if(!used[v]&&v!=h) dfs(v); } } void dfs2(int u) { used2[u]=1; for(int i=0;i<int(g[u].size());++i) { int v=g[u][i].ff; if(!used2[v]) dfs2(v); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n=N,m=M,h=H,k=K; for(int i=0;i<mx;++i) g[i].clear(); memset(used,0,sizeof(used)); for(int i=0;i<m;++i) { g[x[i]].pb({y[i],c[i]}); g[y[i]].pb({x[i],c[i]}); } //check if it's a chain and apply all the special abilities -> m=n-1 && x[i]=i && y[i]=i+1 if(m==n-1) { bool f=1; vector<triple> v; for(int i=0;i<m;++i) { triple cur; cur.u = x[i],cur.v=y[i],cur.w=c[i]; v.pb(cur); if(x[i]+1!=y[i]) { f=0; break; } } if(f) { sort(v.begin(),v.end(),comp); double res=0.0; for(int i=0;i<int(v.size());++i) { triple cur=v[i]; res+=cur.w*1.0; if(cur.v==h) { break; } if(arr[cur.v]==2&&K>0) { res/=2; --K; } else if(!arr[cur.v]) { res=0.0; } } return res; } } if(n==2||n==3) { memset(used2,0,sizeof(used2)); dfs2(0); if(!used2[h]) { return -1; } if(g[0].size()==1) { if(g[0][0].ff==h) { return g[0][0].ss; } else { double res=g[0][0].ss; int cur=g[0][0].ff; if(!arr[cur]) { res=0; } else if(arr[cur]==2 && k>0) { res/=2; } res+=g[h][0].ss; return res; } } else { if(g[0][0].ff==h) { double res1=g[0][0].ss,res2=g[0][1].ss; int cur=g[0][1].ff; if(g[cur].size()==1) return res1; if(!arr[cur]) { res2=0; } else if(arr[cur]==2&&k>0) { res2/=2; } if(g[h][0].ff==0) { res2+=g[h][1].ss; } else { res2+=g[h][0].ss; } return min(res1,res2); } else { double res1=g[0][1].ss,res2=g[0][0].ss; int cur=g[0][0].ff; if(g[cur].size()==1) return res1; if(!arr[cur]) { res2=0; } else if(arr[cur]==2&&k>0) { res2/=2; } if(g[h][0].ff==0) { res2+=g[h][1].ss; } else { res2+=g[h][0].ss; } return min(res1,res2); } } } set<int> s; dfs(0); for(int i=0;i<n;++i) { if(used[i]&&!arr[i]) s.insert(i); } memset(used,0,sizeof(used)); priority_queue<pair<long,int>> pq; for(int i=0;i<n;++i) dis[i]=1e10; for(auto i:s) { pq.push({0,i}); dis[i]=0; } pq.push({0,0}); dis[0]=0; while(!pq.empty()) { int u=pq.top().ss; pq.pop(); if(used[u]) continue; used[u]=1; for(int i=0;i<int(g[u].size());++i) { int v=g[u][i].ff,w=g[u][i].ss; if(dis[u]+w<dis[v]) { dis[v]=dis[u]+w; pq.push({-dis[v],v}); } } } if(dis[h]==1e10) { return -1; } else { return dis[h]; } }
#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...