Submission #782852

#TimeUsernameProblemLanguageResultExecution timeMemory
782852vjudge1Cyberland (APIO23_cyberland)C++17
49 / 100
35 ms9816 KiB
#include<bits/stdc++.h> using namespace std; #define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define endl "\n" #define ll long long #define pb push_back #define uwu 100005 vector<pair<int,int>>adj[uwu]; double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N]; for(int i=0;i<M;i++){ adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]}); } ll int yol[N]; for(int i=0;i<N;i++){ father[i]=-1; yol[i]=1000000000000000000; } priority_queue<tuple<ll int,int,int>> pq; pq.push({(ll int)0,0,-1}); while(pq.size()){ ll int node,once, deg; tie(deg,node,once)=pq.top();deg=-deg; pq.pop(); if(arr[node]==0){ deg=0; } if(yol[node]<=deg)continue; yol[node]=deg; father[node]=once; if(node==H)continue; for(auto u:adj[node]){ ll int kim=u.first, lira=u.second+deg; pq.push({-lira,kim,node}); } } for(int i=0;i<N;i++)adj[i].clear(); if(yol[H]==1000000000000000000)yol[H]=-1; return (1.0)*(double)yol[H]; } double uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){ int kim[3][3]; for(int i=0;i<M;i++){ adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]}); } for(int i=0;i<3;i++){for(int j=0;j<3;j++)kim[i][j]=1000000007;} for(int i=0;i<M;i++){ kim[x[i]][y[i]]=min(kim[x[i]][y[i]],c[i]); kim[y[i]][x[i]]=min(kim[y[i]][x[i]],c[i]); } double yol[N]; for(int i=0;i<N;i++){ yol[i]=1000000000000000000; } if(H==0)return 0; if(N==3){ if(H==2&&kim[0][H]!=1000000007&&kim[0][1]==1000000007) return kim[0][H]/((arr[H]==2&&K)?2.0:1.0); if(H==1&&kim[0][H]!=1000000007&&kim[0][2]==1000000007) return kim[0][H]/((arr[H]==2&&K)?2.0:1.0); priority_queue<tuple<double,int,int>> pq; pq.push({-0.0,0,0}); while(pq.size()){ int node,kac;double deg; tie(deg,node,kac)=pq.top();deg=-deg; pq.pop(); if(arr[node]==0)deg=0; if(arr[node]==2&&kac<K){ deg=deg/2; kac++; } if(yol[node]<=deg)continue; yol[node]=deg; if(node==H)continue; for(auto u:adj[node]){ int ner=u.first;double lira=u.second+deg; pq.push({-lira,ner,kac}); } } if(yol[H]==1000000000000000000)yol[H]=-1; return yol[H]; } if(N==2){ if(kim[0][H]==1000000007)return -1; if(arr[H]==0)return 0; if(arr[H]==2&&K)return kim[0][H]/2.0; return kim[0][H]; } } double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){ int yes=0; for(int i=0;i<N;i++){ if(arr[i]==2){ yes=1;break; } } double cev; if(yes==0)return noiki(N, M, K, H,x, y, c, arr); if(N<=3) cev=uc(N, M, K, H,x, y, c, arr); for(int i=0;i<N;i++)adj[i].clear(); return cev; }

Compilation message (stderr)

cyberland.cpp: In function 'double noiki(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:9:107: warning: variable 'father' set but not used [-Wunused-but-set-variable]
    9 | double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
      |                                                                                                           ^~~~~~
cyberland.cpp: In function 'double uc(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:112:9: warning: 'cev' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |  return cev;
      |         ^~~
#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...