| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1228003 | Dzadzo | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 200000
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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) {
vvp adj(n);
for (int i=0;i<m;i++) {
adj[x[i]].pb({y[i],c[i]});
adj[y[i]].pb({x[i],c[i]});
}
vector <vector <double>> dist(n,vector <double>(31,INF));
dist[h][0]=0;
set <pair <pair <double,int>,int>> st;
st.insert({{dist[h][0],0},h});
while (st.size()) {
int v=st.begin()->S;
int k=st.begin()->F.S;
st.erase(st.begin());
for (auto &[to,w]:adj[v]) {
if (dist[to][k] > dist[v][k]+w ) {
st.erase({{dist[to][k],k},to});
dist[to][k]=dist[v][k]+w;
st.insert({{dist[to][k],k},to});
}
if (arr[to]==2 && k!=30) {
if (dist[to][k+1] > 2*(dist[v][k]+w) ) {
st.erase({{dist[to][k+1],k+1},to});
dist[to][k+1]=2*(dist[v][k]+w);
st.insert({{dist[to][k+1],k+1},to});
}
}
}
}
vb visited(n);
vb res=false;
function<void(int)> dfs = [&](int v) {
if (v==h) {
res=true;
return;
}
visited[v]=true;
for (auto &[to,w]:adj[v]) {
if (!visited[to]) {
dfs(to);
}
}
};
if (!res)return -1;
dfs(0);
double ans=INF;
for (int i=0;i<n;i++) {
if ((!arr[i] || !i) && visited[i]) {
for (int q=0;q<=min(30,K);q++)ans=min(ans,dist[i][q] / (double)(1ll<<q));
}
}
return ans;
}
// int main() {
// // cout<<solve(3,0,30,2,{},{},{},{});
// }
/*
3 0 30
2
1 0 1
*/