Submission #797984

#	Time	Username	Problem	Language	Result	Execution time	Memory
797984		sentheta	Cyberland (APIO23_cyberland)	C++17	68 / 100	3079 ms	262020 KiB

cyberland

#include "cyberland.h"
#ifdef VANWIJ
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define float long double


const float INF = 1e18;
const int N = 1e5+5;
const int K = 80;

int n, m, k, tar;
V<pii> adj[N];

float d[N][K][2];

double solve(int _n,int _m,int _k,int _tar,V<int> mx,V<int> my,V<int> mc,V<int> arr){
	n = _n; m = _m; k = _k; tar = _tar;
	
	k = min(k, K-2);
	rep(i,0,n){
		adj[i].clear();
		rep(j,0,K) rep(t,0,2){
			d[i][j][t] = INF;
		}
	}
	
	rep(i,0,m){
		adj[mx[i]].push_back({my[i], mc[i]});
		adj[my[i]].push_back({mx[i], mc[i]});
	}
	
	float ans = INF;
	
	// {-moves, -dist, node, used_ability}
	priority_queue<tuple<int,float,int,bool>> pq;
	pq.push({0,0,0,0});
	while(!pq.empty()){
		auto[mov,dist,x,used] = pq.top(); pq.pop();
		mov *= -1; dist *= -1;
		if(d[x][mov][used] <= dist) continue;
		d[x][mov][used] = dist;
		
		assert(0<=x && x<n);
		assert(0<=mov && mov<=k);
		
		if(x==tar){
			ans = min(ans, dist);
			continue;
		}
		
		if(!used && arr[x]==0){
			pq.push({-mov, 0, x, 1});
		}
		if(!used && mov<k && arr[x]==2){
			pq.push({-(mov+1), -(dist/2), x, 1});
		}
		
		
		for(auto[y,w] : adj[x]){
			pq.push({-mov, -(dist+w), y, 0});
		}
	}
	
	if(ans > N*1e9) return -1;	
	return ans;
}

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