Submission #976821

#TimeUsernameProblemLanguageResultExecution timeMemory
976821AlperenT_Cyberland (APIO23_cyberland)C++17
0 / 100
3016 ms110492 KiB
#include "cyberland.h" #include <vector> #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #define pb push_back #define F first #define S second #define all(a) a.begin(),a.end() #define pii pair <int,int> #define PII pair<pii , pii> #define ld long double #define ll long long #define sz(v) (int)v.size() #define rep(i , a , b) for(int i=a;i <= b;i++) #define per(i , a , b) for(int i=a;i >= b;i--) using namespace std ; const ll maxn = 2e5+10 , N = 1e5 +1 , maxq = 202 , inf = 1e18 , maxk = 2022 , mod =1e9+7 ; ld dis[maxn][102] ;int mark[maxn]; vector <pair<int,ld> > G[maxn] ; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> t) { rep(i , 0 ,m-1){ G[x[i]].pb({y[i] , c[i]}); G[y[i]].pb({x[i] , c[i]}) ; } k = min(k , 100); rep(j , 0 , n-1)rep(z , 0 , k)dis[j][z] = inf ; dis[h][0] = 0 ; ld ans =inf; rep(i , 0 , k){ priority_queue <pair<ld,int> > pq ; rep(j , 0 , n-1){ pq.push({-dis[j][i] , j}) ; mark[j] =0 ; } while(sz(pq)){ int v = pq.top().S ;pq.pop(); if(mark[v] == 1)continue; mark[v] = 1; for(auto a : G[v]){ if(dis[a.F][i] > dis[v][i]+a.S){ dis[a.F][i] = dis[v][i] + a.S ; pq.push({-dis[a.F][i] , a.F}); } } } rep(j , 0 , n-1){ rep(z ,0 , sz(G[j])-1){ G[j][z].S /= 2.0000000 ; } } rep(j , 0 , n-1){ if(j == 0 || t[j] == 0) ans = min(ans , dis[j][i]) ; } rep(j , 0 , n-1){ if(t[j]==2){ dis[j][i+1] = dis[j][i] ; } } } if(ans == inf)return -1 ; 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...