Submission #1197579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197579		nouka28	Cyberland (APIO23_cyberland)	C++20	0 / 100	1091 ms	36524 KiB

cyberland

#include "cyberland.h"

#include <vector>

#include<bits/stdc++.h>
using namespace std;

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;

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) {
	vector<vector<pair<int,int>>> g(N);
	rep(i,M){
		g[x[i]].push_back({y[i],c[i]});
		g[y[i]].push_back({x[i],c[i]});
	}
	vector<bool> flg(N);
	{
		stack<int> q;
		q.push(0);
		while(q.size()){
			int p=q.top();q.pop();
			flg[p]=1;
			for(auto&&[e,c]:g[p]){
				if(flg[e])continue;
				q.push(e);
			}	
		}
		if(!flg[H]){
			return -1;
		}
	}

	K=min(K,50);
	vector<vector<double>> d(K+1,vector<double>(N,1e18));
	pqmin<tuple<double,int,int>> pq;
	d[0][0]=0;pq.push({0,0,0});
	rng(i,1,N){
		if(flg[i]&&arr[i]==0){
			d[0][i]=0;
			pq.push({0,0,i});
		}
	}

	while(pq.size()){
		auto[cost,k,p]=pq.top();pq.pop();
		
		for(auto&&[e,c]:g[p]){
			if(d[k][e]>cost+c){
				d[k][e]=cost+c;
				pq.push({d[k][e],k,e});
			}

			if(arr[e]==2&&k<K){
				double t=(cost+c)/double(2.0);
				if(d[k+1][e]>t){
					d[k+1][e]=t;
					pq.push({d[k+1][e],k+1,e});
				}
			}
		}
	}

	double ans=1e18;
	rep(i,K+1)ans=min(ans,d[i][H]);

	if(ans>1e17)return -1;
	else return ans;
}

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