Submission #797992

#	Time	Username	Problem	Language	Result	Execution time	Memory
797992		sentheta	Cyberland (APIO23_cyberland)	C++17	100 / 100	1589 ms	62868 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 double


const float INF = 1e18;
const float E = 1e-8;
const int N = 1e5+5;
const int K = 69;

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

// {-moves, -dist, node}
priority_queue<tuple<int,float,int>> pq;
float d[N][K];
void relax(int mov,float dist,int node){
	if(d[node][mov] <= dist) return;
	d[node][mov] = dist;
	pq.push({-mov,-dist,node});
}

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){
			d[i][j] = 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;
	
	relax(0,0,0);
	while(!pq.empty()){
		auto[mov,dist,x] = pq.top(); pq.pop();
		mov *= -1; dist *= -1;
		if(abs(d[x][mov]-dist) > E) continue;
		
		assert(0<=x && x<n);
		assert(0<=mov && mov<=k);
		
		if(x==tar){
			ans = min(ans, dist);
			continue;
		}
		
		if(arr[x]==0){
			relax(mov, 0, x);
		}
	
		for(auto[y,w] : adj[x]){
			relax(mov, dist+w, y);
			
			if(mov<k && arr[x]==2){
				relax(mov+1, dist/2+w, y);
			}
		}
	}
	
	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: 29 / 29
• Subtask 8: 3 / 3