Submission #979524

#TimeUsernameProblemLanguageResultExecution timeMemory
979524phoenix0423Cyberland (APIO23_cyberland)C++17
0 / 100
559 ms55160 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define pb push_back #define eb emplace_back #define f first #define s second #include "cyberland.h" const int maxn = 2e5 + 5; const double INF = 1e18; const double eps = 1e-9; vector<pll> adj[maxn]; int par[maxn]; double dist[maxn][81]; int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);} void unite(int x, int y){ x = root(x), y = root(y); if(x == y) return; par[x] = y; } struct info{ double d; int pos, l; info(){} info(double _d, int _pos, int _l) : d(_d), pos(_pos), l(_l){} bool operator < (const info& other) const{ return d < other.d; } bool operator > (const info& other) const{ return d > other.d; } }; priority_queue<info, vector<info>, greater<info>> q; 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) { k = min(k, 80); for(int i = 0; i < n; i++) adj[i].clear(), par[i] = i; for(int i = 0; i < m; i++){ adj[x[i]].pb({y[i], c[i]}); adj[y[i]].pb({x[i], c[i]}); unite(x[i], y[i]); } if(root(0) != root(h)) return -1; for(int i = 1; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = INF; // arr[0] = 0; for(int i = 0; i < n; i++){ if(arr[i] == 0 && root(i) == root(0)){ for(int j = 0; j <= k; j++) dist[i][j] = 0; q.push(info(0, i, 0)); } } while(!q.empty()){ auto [d, pos, l] = q.top(); q.pop(); if(dist[pos][l] < d || pos == h) continue; for(auto [x, w] : adj[pos]){ if(dist[x][l] > d + w){ dist[x][l] = d + w; q.push(info(dist[x][l], x, l)); } } if(arr[pos] == 2 && l < k){ d /= 2, l++; if(dist[pos][l] < d) continue; for(auto [x, w] : adj[pos]){ if(dist[x][l] > d + w){ dist[x][l] = d + w; q.push(info(dist[x][l], x, l)); } } } } double ans = INF; for(int i = 0; i <= k; i++) ans = min(ans, dist[h][i]); 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...