Submission #967030

#TimeUsernameProblemLanguageResultExecution timeMemory
967030dubabubaCyberland (APIO23_cyberland)C++17
15 / 100
626 ms44220 KiB
#include <bits/stdc++.h> #include "cyberland.h" #pragma GCC optimize("O3") #pragma GCC target("lzcnt", "popcnt") using namespace std; typedef double dbl; typedef vector<int> vi; typedef long long i64; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxk = 32; const int mxn = 1e5 + 10; vector<pii> adj[mxn]; dbl dis[mxk][mxn]; bool vis[mxn]; int H; template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; } template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; } double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) { ::H = H; for(int i = 0; i < N; i++) adj[i].clear(); for(int i = 0; i < M; i++) { adj[x[i]].push_back(MP(y[i], c[i])); adj[y[i]].push_back(MP(x[i], c[i])); } priority_queue<pair<pair<dbl, int>, int>> pq; for(int i = 0; i < N; i++) for(int j = 0; j <= K && j < mxk; j++) dis[j][i] = -1.0; for(int i = 0; i < N; i++) vis[i] = 0; queue<int> q; vis[0] = 1; q.push(0); pq.push(MP(MP(0.0, 0), 0)); while(q.size()) { int u = q.front(); q.pop(); if(arr[u] == 0) pq.push(MP(MP(0.0, 0), u)); for(pii p : adj[u]) { int v = p.ff; if(!vis[v]) { vis[v] = 1; q.push(v); } } } while(pq.size()) { dbl d = -pq.top().ff.ff; int k = -pq.top().ff.ss; int u = pq.top().ss; pq.pop(); if(dis[k][u] > -1.0) continue; dis[k][u] = d; for(pii p : adj[u]) { int v = p.ff; dbl c = p.ss; if(v == 0 || arr[v] == 0) continue; // if(dis[k][v] == -1.0) pq.push(MP(MP(-(d + c), -k), v)); if(arr[v] == 2 && k < K && k < mxk) // if(dis[k + 1][v] == -1.0) pq.push(MP(MP(-(d + c) / 2.0, -k - 1), v)); } } dbl ans = 1e18; for(int k = 0; k < mxk && k <= K; k++) if(dis[k][H] != -1) ono_min(ans, dis[k][H]); if(ans != 1e18) return ans; return -1; } /* 5 3 2 30 2 1 2 1 1 2 12 2 0 4 4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4 3 3 30 2 1 2 1 0 1 1 1 2 1 2 0 1 5 5 30 4 1 2 2 2 1 0 1 1 1 2 1000 2 3 1 3 1 1 2 4 1 5 5 30 4 1 1 2 1 1 0 1 4 1 2 2 2 3 1 3 1 1 2 4 1 4 4 30 3 1 2 1 1 0 1 110 0 2 50 2 3 10 1 3 1 */
#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...