Submission #975873

#TimeUsernameProblemLanguageResultExecution timeMemory
975873gaga999Cyberland (APIO23_cyberland)C++17
100 / 100
1324 ms13604 KiB
// #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define size(x) (int)x.size() #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef __int128_t lll; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef pair<llt, int> pli; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } inline char gc() { const static int SZ = 1 << 16; static char buf[SZ], *p1, *p2; if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2)) return -1; return *p1++; } void rd() {} template <typename T, typename... U> void rd(T &x, U &...y) { x = 0; bool f = 0; char c = gc(); while (!isdigit(c)) f ^= !(c ^ 45), c = gc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); f && (x = -x), rd(y...); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } typedef pair<double, int> pdl; 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> ar) { vector<pii> eg[n]; for (int i = 0; i < m; i++) eg[x[i]].pb(c[i], y[i]), eg[y[i]].pb(c[i], x[i]); vector<double> ans(n, 1e18); vector<bool> vd(n, 0); { ans[0] = 0; queue<int> q; q.push(0), vd[0] = 1; while (!q.empty()) { int u = q.front(); q.pop(); if (u == H) continue; if (!ar[u]) ans[u] = 0; for (pii v : eg[u]) if (!vd[v.S]) q.push(v.S), vd[v.S] = 1; } if (!vd[H]) return -1; } auto dij = [&]() -> void { priority_queue<pdl, vector<pdl>, greater<pdl>> pq; for (int i = 0; i < n; i++) if (ans[i] < 1e16) pq.emplace(ans[i], i); fill(iter(vd), 0); while (!pq.empty()) { pdl tp = pq.top(); pq.pop(); if (vd[tp.S]) continue; vd[tp.S] = 1; if (tp.S == H) continue; for (pii v : eg[tp.S]) if (!vd[v.S] && ans[tp.S] + v.F < ans[v.S]) pq.emplace(ans[v.S] = ans[tp.S] + v.F, v.S); } for (int u = 0; u < n; u++) { if (ar[u] != 2 || !vd[u]) continue; double mn = 1e18; for (pii v : eg[u]) if (vd[v.S] && v.S != H) tmin(mn, (ans[v.S] + v.F) / 2.0); pq.emplace(mn, u); } while (!pq.empty()) tmin(ans[pq.top().S], pq.top().F), pq.pop(); }; for (int t = min(k, 80); t >= 0; t--) dij(); return ans[H]; } // signed main() // { // int n, m, k, h; // rd(n, m, k, h); // vector<int> ar(n), x(m), y(m), c(m); // for (int i = 0; i < n; i++) // rd(ar[i]); // for (int i = 0; i < m; i++) // rd(x[i], y[i], c[i]); // cout << solve(n, m, k, h, x, y, c, ar) << '\n'; // }
#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...