Submission #932010

#	Time	Username	Problem	Language	Result	Execution time	Memory
932010		Edu175	Cyberland (APIO23_cyberland)	C++17	44 / 100	1130 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;
typedef pair<ld,ii> node;
const ll MAXN=1e5+5;

vector<pair<ll,ld>>g[MAXN];
ll h;
ll vis[MAXN];
void dfs(ll x){
	vis[x]=1;
	for(auto [y,sg]:g[x])if(!vis[y]&&y!=h)dfs(y);
}
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,k=K;
    h=H;
    vector<ll>a(n);
    fore(i,0,n)a[i]=arr[i];
    fore(i,0,n){
    	g[i].clear();
    	vis[i]=0;
    }
    fore(i,0,m){
    	g[x[i]].pb({y[i],c[i]});
    	g[y[i]].pb({x[i],c[i]});
    }
    dfs(0);
    ld d[n][k+5];
    fore(i,0,n)fore(j,0,k+5)d[i][j]=-1;
    priority_queue<node,vector<node>,greater<node>>pq;
    a[0]=0;
    fore(i,0,n)if(vis[i]&&!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;
    	if(x==h)return w;
    	//cout<<x<<" "<<u<<": "<<w<<"\n";
    	for(auto [y,w]:g[x]){
    		ld nd=d[x][u]+w/double(1ll<<u);
    		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 -1;
}

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