| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 933520 | JuanJL | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;
ll n,m,k,h;
vector<vector<pll>> adj;
vector<ll> type;
vector<bool> disp;
void dfs(ll nd){
if(disp[nd]) return;
disp[nd]=1;
if(nd==h) return;
for(auto i:adj[nd]) dfs(i.fst);
}
double Dijkstra(){
double dist[n+5][k+1];
forn(i,0,n+5) forn(j,0,k+1) dist[i][j]=-1;
priority_queue<pair<double,pair<ll,ll>>> pq;
pq.push({0,{0,0}});
forn(i,0,k+1) dist[0][i]=0;
forn(i,0,n){
if(type[i]==0&&disp[i]){
pq.push({0,{i,0}});
forn(j,0,k+1) dist[i][j]=0;
}
}
while(!pq.empty()){
double cost = pq.top().fst*-1;
ll nd = pq.top().snd.fst;
ll p2 = pq.top().snd.snd;
pq.pop();
if(cost>dist[nd][p2]) continue;
if(nd==h) continue;
for(auto i:adj[nd]){
ll ndV = i.fst;
double nCost = i.snd+cost;
if(type[ndV]==0) continue;
if(nCost<dist[ndV][p2]||dist[ndV][p2]==-1){
dist[ndV][p2]=nCost;
pq.push({dist[ndV][p2]*-1,{ndV,p2}});
}
if(type[ndV]==2&&p2+1<min((ll)k+1,(ll)k+1)){
nCost/=2;
if(nCost<dist[ndV][p2+1]||dist[ndV][p2+1]==-1){
dist[ndV][p2+1]=nCost;
pq.push({dist[ndV][p2+1]*-1,{ndV,p2+1}});
}
}
}
}
double res = -1;
forn(i,0,k+1) if(dist[h][i]!=-1&&(res>dist[h][i]||res==-1)) res = dist[h][i];
return (double)res;
}
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){
n=N;m=M;k=min(K,(ll)75);h=H;
adj.clear();
adj.resize(n);
type.clear();
type.resize(n);
disp.clear();
disp.resize(n,0);
forn(i,0,SZ(x)) adj[x[i]].pb({y[i],c[i]}),adj[y[i]].pb({x[i],c[i]});
forn(i,0,n) type[i]=arr[i];
dfs(0);
return Dijkstra();
}