Submission #932003

#	Time	Username	Problem	Language	Result	Execution time	Memory
932003		Edu175	Cyberland (APIO23_cyberland)	C++17	15 / 100	1514 ms	2097152 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,apio=b;i<apio;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto slkdh:v)cout<<slkdh<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;

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) {
    ll n=N,m=M,h=H,k=K;
    vector<ll>a(n);
    fore(i,0,n)a[i]=arr[i];
    vector<ii>g[n];
    fore(i,0,m){
    	g[x[i]].pb({y[i],c[i]});
    	g[y[i]].pb({x[i],c[i]});
    }
    ld d[n][k+5];
    fore(i,0,n)fore(j,0,k+5)d[i][j]=-1;
    priority_queue<pair<ld,ii>>pq;
    a[0]=0;
    fore(i,0,n)if(!a[i]){
    	pq.push({-0,{i,0}});
    	d[i][0]=0;
    }
    while(SZ(pq)){
    	auto [w,par]=pq.top(); pq.pop(); w=-w;
    	auto [x,u]=par;
    	if(d[x][u]<w)continue;
    	//cout<<x<<" "<<u<<": "<<w<<"\n";
    	for(auto [y,w]:g[x]){
    		ld nd=d[x][u]+w;
    		if(d[y][u]==-1||nd<d[y][u])
    			d[y][u]=nd,pq.push({-nd,{y,u}});
    		if(a[y]==2){
    			nd/=2.0;
    			ll v=u+1;
    			if(v>k)continue;
    			if(d[y][v]==-1||nd<d[y][v])
    				d[y][v]=nd,pq.push({-nd,{y,v}});
    		}
    	}
    }
    ld res=-1;
    fore(i,0,k+1){
    	//cout<<i<<" "<<d[h][i]<<"\n";
    	if(d[h][i]!=-1&&(res==-1||d[h][i]<res))res=d[h][i];
    }
    return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3