제출 #1197602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197602		nouka28	Cyberland (APIO23_cyberland)	C++20	15 / 100	3109 ms	526352 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>>;

using lint=__int128_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<lint>> d(K+1,vector<lint>(N,lint(1)<<120));
	pqmin<tuple<lint,int,int>> pq;

	rep(i,N){
		if(i==0||arr[i]==0){
			d[0][i]=0;
			pq.push({0,0,i});
		}
	}

	while(pq.size()){
		auto[cost,k,p]=pq.top();pq.pop();
		if(d[k][p]<cost)continue;

		for(auto&&[e,c]:g[p]){
			lint nc=cost+(lint(c)<<k);
			if(d[k][e]>cost+c){
				d[k][e]=nc;
				pq.push({nc,k,e});
			}

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

	double ans=1e18;
	rep(i,K+1){
		long double t=(long double)(d[i][H])/(long double)(lint(1)<<i);
		if(ans>t)ans=t;
	}

	return ans;
}

• 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