Submission #1000819

#TimeUsernameProblemLanguageResultExecution timeMemory
1000819underwaterkillerwhaleCyberland (APIO23_cyberland)C++17
0 / 100
3073 ms30468 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define se second #define fs first #define mp make_pair #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 1e5 + 7; const int Mod = 1e9 +7; const int szBL = 50; const ll INF = 1e13; const int BASE = 137; struct toEdge { int v; ll w; }; int n, m, K, H; int a[N]; vector<toEdge> ke[N]; double dp[N][35]; bool canGo[N]; void BFS () { queue<int> Q; Q.push(1); canGo[1] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(); iter (&id, ke[u]) { if (canGo[id.v] == 0) { canGo[id.v] = 1; if (id.v != H) Q.push(id.v); } } } } double algo () { BFS(); if (canGo[H] == 0) { return -1; } struct Data { ll u, k; long double val; }; struct cmp { bool operator () (Data A, Data B) { return A.val > B.val; } }; priority_queue<Data, vector<Data>, cmp> pq; rep (i, 1, n) rep (k, 0, min(K, 30)) dp[i][k] = INF; rep (i, 1, n) if ((i == 1) || (a[i] == 0 && canGo[i])) { pq.push({i, 0, 0}); dp[i][0] = 0; } while (!pq.empty()) { Data cur = pq.top(); int u = cur.u, k = cur.k; pq.pop(); iter (&id, ke[u]) { int v = id.v; ll w = id.w; if (a[v] == 0) continue; else { if (dp[v][k] > dp[u][k] + w) { dp[v][k] = dp[u][k] + w; pq.push({v, k, dp[v][k]}); } if (a[v] == 2 && k < 30 && dp[v][k + 1] > (dp[u][k] + w) / 2) { dp[v][k + 1] = (dp[u][k] + w) / 2; pq.push({v, k + 1, dp[v][k + 1]}); } } } } double res = INF; rep (i, 0, min(K, 30)) { res = min(res, dp[H][i]); } return res; } double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) { //void solution() { // cin >> n >> m >> K >> H; // rep (i, 1, n) cin >> a[i]; // rep (i, 1, m) { // int u, v, w; // cin >> u >> v>> w; // ++u, ++v; // ke[u].push_back({v, w}); // ke[v].push_back({u, w}); // } n = _n; m = _m; K = _K; H = _H; ++H; rep (i, 1, n) { a[i] = _A[i - 1]; } rep (i, 0, m - 1) { int u = _U[i], v = _V[i], w = _W[i]; ++u, ++v; ke[u].push_back({v, w}); ke[v].push_back({u, w}); } return algo(); } //#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); //int main () { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //// file ("c"); // int num_Test = 1; // cin >> num_Test; // while (num_Test--) // solution(); //} /* 1 3 2 30 2 1 2 1 1 2 12 2 0 4 3 2 0 1 5 0 2 5 1 1 2 */
#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...