Submission #847760

#TimeUsernameProblemLanguageResultExecution timeMemory
847760KN200711Cyberland (APIO23_cyberland)C++17
44 / 100
67 ms27592 KiB
#include "cyberland.h" # include <bits/stdc++.h> # define fi first # define se second using namespace std; bool vis[100001]; vector< pair<int, double> > edge[100001]; int h1; void dfs(int a) { vis[a] = 1; if(a == h1) return; for(auto p : edge[a]) { if(!vis[p.fi]) dfs(p.fi); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { K = min(K, 70); h1 = H; for(int i=0;i<N;i++) { vis[i] = 0; edge[i].clear(); } for(int i=0;i<M;i++) { edge[x[i]].push_back(make_pair(y[i], (double) c[i])); edge[y[i]].push_back(make_pair(x[i], (double) c[i])); } dfs(0); vector< vector<double> > dp; dp.resize(K + 1); for(int i=0;i<=K;i++) { dp[i].resize(N); for(int c=0;c<N;c++) dp[i][c] = -1; } priority_queue< pair<int, pair<double, int> > > PQ; for(int d=0;d<N;d++) { if(d == 0 || (arr[d] == 0 && vis[d])) PQ.push(make_pair(0, make_pair(0, d))); } while(!PQ.empty()) { double a = PQ.top().se.fi; int nm = -PQ.top().fi, pos = PQ.top().se.se; PQ.pop(); if(dp[nm][pos] != -1) continue; dp[nm][pos] = -a; // cout<<pos<<" "<<-nm<<" "<<-a<<endl; if(pos == H) break; for(auto p : edge[pos]) { if(arr[p.fi] == 0) continue; else if(arr[p.fi] == 1 && dp[nm][p.fi] == -1) PQ.push(make_pair(-nm, make_pair((double) a - ((double) p.se), p.fi))); else if(arr[p.fi] == 2) { if(nm + 1 <= K && dp[nm+1][p.fi] == -1) PQ.push(make_pair(-nm-1, make_pair(((double) a - (double) p.se) / ((double) 2), p.fi))); if(dp[nm][p.fi] == -1) PQ.push(make_pair(-nm, make_pair(((double) a - (double) p.se), p.fi))); } } } double ans = 1e18; for(int v=0;v<=K;v++) { if(dp[v][H] != (double) -1) ans = min(ans, dp[v][H]); } if(ans == 1e18) ans = -1; 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...