Submission #1001995

#TimeUsernameProblemLanguageResultExecution timeMemory
1001995underwaterkillerwhaleCyberland (APIO23_cyberland)C++17
97 / 100
3079 ms397352 KiB
#ifdef ONLINE_JUDGE #include "cyberland.h" #endif #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 = 1e15; const int BASE = 137; struct toEdge { int v, w; }; int n, m, K, H; int a[N]; vector<toEdge> ke[N]; namespace sub1 { double dist[N]; double solution() { rep (i, 1, n) dist[i] = INF; priority_queue<pair<double, int>, vector<pair<double,int>>, greater<pair<double, int>> > Q; Q.push({0, 1}); dist[1] = 0; while (!Q.empty()) { int u = Q.top().se; Q.pop(); iter (&id, ke[u]) { int v = id.v, w = id.w; double delta = dist[u] + w; if (a[v] == 2) delta /= 2.0; else if (a[v] == 0) delta = 0; if (dist[v] > delta) { dist[v] = delta; if (v != H) { Q.push({dist[v], v}); } } } } if (dist[H] == INF) return -1; else return dist[H]; } } namespace sub160907 { struct Data { ll u, k; double val; }; struct cmp { bool operator () (Data A, Data B) { return A.val > B.val; } }; double dp[N][70]; bool canGo[N]; double PW[70]; void BFS () { rep (i, 1, n) canGo[i] = 0; 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]) { canGo[id.v] = 1; if (id.v != H) Q.push(id.v); } } } } double solution() { rep (i, 1, n) rep (k, 0, K) dp[i][k] = INF; BFS(); priority_queue<Data, vector<Data>, cmp> pq; rep (i, 1, n) { if (i == 1 || (a[i] == 0 && canGo[i] == 1)) { rep (k, 0, K) { dp[i][k] = 0; pq.push({i, k, 0}); } } } PW[0] = 1; rep (i, 1, K) PW[i] = PW[i - 1] / 2; ll res = INF; while (!pq.empty()) { int u = pq.top().u, k = pq.top().k; if (u == H && k == 0) { return dp[u][k]; } pq.pop(); iter (&id, ke[u]) { ll v = id.v, w = id.w; if (a[v] == 0) continue; if (a[v] == 1) { if (dp[v][k] > dp[u][k] + 1.0 * w * PW[k]) { dp[v][k] = dp[u][k] + 1.0 * w * PW[k]; if (v != H || k == 0) pq.push({v, k, dp[v][k]}); } } else if (a[v] == 2) { if (dp[v][k] > dp[u][k] + 1.0 * w * PW[k]) { dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k); if (v != H || k == 0) pq.push({v, k, dp[v][k]}); } if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w * PW[k]) { dp[v][k - 1] = dp[u][k] + 1.0 * w * PW[k]; if (v != H || k == 0) pq.push({v, k - 1, dp[v][k - 1]}); } } } } return -1; } } double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) { n = _n; m = _m; K = _K; H = _H; K = min(K, 65); ++H; rep (i ,1, n) ke[i].clear(); 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}); } // if (n <= 3 && K <= 30) // return sub1 :: solution(); // else return sub160907 :: solution(); } //void solution() { // cin >> n >> m >> K >> H; // ++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}); // } // cout << sub1 :: solution () <<"\n"; // cout << sub160907 :: solution () <<"\n"; //} //#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 1 4 4 30 3 1 1 2 1 0 1 5 0 2 5 1 3 2 2 3 4 3 2 0 1 5 0 2 5 1 1 2 */

Compilation message (stderr)

cyberland.cpp: In function 'double sub160907::solution()':
cyberland.cpp:110:12: warning: unused variable 'res' [-Wunused-variable]
  110 |         ll res = INF;
      |            ^~~
#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...