제출 #984878

#제출 시각아이디문제언어결과실행 시간메모리
984878javotaz사이버랜드 (APIO23_cyberland)C++17
15 / 100
244 ms14256 KiB
// In the Name of Allah #include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") typedef long long ll; typedef pair<double, int> pd; #define F first #define S second #define pii pair<int, int> #define pb push_back #define pp pop_back #define all(x) x.begin(), x.end() const int N = 1e5 + 12, K = 76; vector<pii> g[N]; int n, m, k, h, a[N]; double ans; bool mrk[N][K]; void find_ans() { ans = 1e18; priority_queue<pd, vector<pd>, greater<pd>> q; q.push({0, 0}); for (int i = 1; i < n; i++) if (!a[i]) q.push({0, i}); while (!q.empty()) { auto tmp = q.top(); q.pop(); int u = tmp.S % n, ck = tmp.S / n; double w = tmp.F; if (u == h) ans = min(ans, w); if (mrk[u][ck]) continue; mrk[u][ck] = true; for (auto i: g[u]) if (a[i.F] && !mrk[i.F][ck + (a[i.F] == 2)]) { if (a[i.F] == 1) q.push({w + i.S, i.F + ck * n}); else if (ck + 1 <= k) q.push({(w + i.S) / 2, i.F + (ck + 1) * n}); } } if (ans == 1e18) ans = -1; } double solve(int ns, int ms, int ks, int hs, vector<int> xs, vector<int> ys, vector<int> ws, vector<int> as) { n = ns, m = ms, k = min(ks, 75), h = hs; for (int i = 0; i < m; i++) g[xs[i]].pb({ys[i], ws[i]}), g[ys[i]].pb({xs[i], ws[i]}); for (int i = 0; i < n; i++) a[i] = as[i]; find_ans(); for (int i = 0; i < n; i++) { g[i].clear(); for (int j = 0; j <= k; ++j) mrk[i][j] = false; } 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...