제출 #894883

#제출 시각아이디문제언어결과실행 시간메모리
894883n0sk1ll사이버랜드 (APIO23_cyberland)C++17
44 / 100
75 ms181332 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //const int mod=1'000'000'000; //Note to self: Check for overflow int k,n; vector<vector<pii>> g(100005); double dub[2][102][100005]; //min depth to each version of every node bool vis[2][102][100005]; bool vist[100005]; //temporary void dfs(int p) { if (vist[p]) return; vist[p]=true; for (auto it : g[p]) dfs(it.xx); } void add_edge(int u, int v, int w) { g[u].push_back({v,w}); } double solve(int N, int m, int K, int H, std::vector<int> u, std::vector<int> v, std::vector<int> w, std::vector<int> arr) { n=N; k=min(K,100); ff(i,0,n) g[i].clear(); ff(stat,0,2) fff(kolko,0,k) ff(i,0,n) dub[stat][kolko][i]=0,vis[stat][kolko][i]=false; ff(i,0,n) vist[i]=false; ff(i,0,m) { if (u[i]==H) add_edge(v[i],u[i],w[i]); else if (v[i]==H) add_edge(u[i],v[i],w[i]); else add_edge(u[i],v[i],w[i]),add_edge(v[i],u[i],w[i]); } dfs(0); if (!vist[H]) return -1; vector<int> sources={0}; ff(i,1,n) if (vist[i] && arr[i]==0) sources.push_back(i); #define typ pair<double,pair<int,bool>> priority_queue<typ,vector<typ>,greater<typ>> pq[102]; for (auto it : sources) pq[0].push({0,{it,false}}); fff(kolko,0,k) while (!pq[kolko].empty()) { double d=pq[kolko].top().xx; int p=pq[kolko].top().yy.xx; bool stat=pq[kolko].top().yy.yy; pq[kolko].pop(); if (vis[stat][kolko][p]) continue; vis[stat][kolko][p]=true; dub[stat][kolko][p]=d; for (auto it : g[p]) pq[kolko].push({d+it.yy,{it.xx,false}}); if (arr[p]==2 && !stat && kolko<k) pq[kolko].push({d/2,{p,true}}); } double ans=1e18; ff(stat,0,2) fff(i,0,k) if (vis[stat][i][H]) ans=min(ans,dub[stat][i][H]); 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...