제출 #862795

#제출 시각아이디문제언어결과실행 시간메모리
862795Berryisbetter사이버랜드 (APIO23_cyberland)C++17
8 / 100
2201 ms309428 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; using ll = long double; using vll = vector<ll>; using vvll = vector<vll>; const ll INF = 1e16; vll v; vector<vector<pair<ll, ll>>>g; ll h,n; void dfs(ll x) { if (v[x]++) return; if ((int)x%(int)n==h) return; for (auto i : g[x]) { dfs(i.first); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { ll m = M, k = min(K, 32) + 1; h = H, n = N; v = vll(n*k); g=vector<vector<pair<ll, ll>>>(n*k); for (ll j = 0; j < k; j++) { for (ll i = 0; i < m; i++) { g[x[i] + j * n].push_back({ y[i] + j * n, c[i]/(1<<(int)j)}); g[y[i] + j * n].push_back({ x[i] + j * n, c[i] / (1 << (int)j)}); if (j && arr[x[i]] == 2) { g[x[i] + j * n].push_back({ y[i] + (j-1) * n, c[i] / (1 << (int)j) }); } if (j && arr[y[i]] == 2) { g[y[i] + j * n].push_back({ x[i] + (j - 1) * n, c[i] / (1 << (int)j) }); } } } for (ll i = 0; i < k; i++) { dfs(i*n); } v = vll(n * k, INF); priority_queue<pair<ll,ll>, std::vector<pair<ll,ll>>, std::greater<pair<ll,ll>>> q; q.push({ 0,0 }); v[0] = 0; for (ll j = 0; j < k; j++) { for (ll i = 0; i < n; i++) { if (arr[i] == 0&&v[i+j*n]) { q.push({ 0, i + j * n }); v[i + j * n] = 0; } } } while (q.size()) { pair<ll, ll> he = q.top(); q.pop(); if (v[he.second] < he.first||he.second==h) { continue; } for (auto i : g[he.second]) { if (v[i.first] <= he.first + i.second) { continue; } v[i.first] = he.first + i.second; q.push({ v[i.first],i.first }); } } return v[h]; }
#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...