Submission #977589

#TimeUsernameProblemLanguageResultExecution timeMemory
977589TsaganaCyberland (APIO23_cyberland)C++17
8 / 100
243 ms9080 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie(); #define all(x) x.begin(), x.end() //#define int long long #define vi vector<int> #define pi pair<int, int > #define pq priority_queue #define lb lower_bound #define ub upper_bound #define pb push_back #define eb emplace_back #define mset multiset #define F first #define S second #define pid pair<int, double> #define pdi pair<double, int> using namespace std; // START vector<pid> adj[100001]; double mindis[100001]; bool reach[100001]; int h, n; void dfs(int s) { reach[s] = 1; if (s == h) return; for (auto i: adj[s]) if(!reach[i.F]) dfs(i.F); } void dij(vector<int> &arr) { pq<pdi> q; for (int i = 0; i < n; i++) { if (reach[i] && mindis[i] < 1e18) q.push({mindis[i], i}); } vector<bool> vis(n, 0); while(!q.empty()) { int s = q.top().S; q.pop(); if (vis[s]) continue; vis[s] = 1; if (s == h) continue; for (auto i: adj[s]) { if(reach[i.F] && !vis[i.F] && mindis[i.F] > mindis[s] + i.S) { mindis[i.F] = mindis[s] + i.S; q.push({mindis[i.F], i.F}); } } } vector<pid> tmp; for (int u = 0; u < n; u++) { double mn = mindis[u]; if (reach[u] && arr[u]==2) for(auto i: adj[u]) if(reach[i.F] && i.F != h) mn = min(mn, (mindis[i.F] + i.S) / 2.0); if (mn < mindis[u]) tmp.pb({u, mn}); } for(auto i:tmp) mindis[i.F] = min(mindis[i.F], i.S); } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { h = H; n = N; K = min(K, 70); for (int i = 0; i < N; i++) { adj[i].clear(); reach[i] = 0; mindis[i] = 1e18; } for(int i = 0; i < M; i++) { adj[x[i]].pb({y[i], (double)c[i]}); adj[y[i]].pb({x[i], (double)c[i]}); } dfs(0); if(!reach[H]) return -1; mindis[0] = 0; for (int i = 1; i < N; i++) if (reach[i] && !arr[i]) mindis[i] = 0; for (int i = 0; i <= K; i++) dij(arr); return mindis[H]; } //END
#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...