Submission #797951

#	Time	Username	Problem	Language	Result	Execution time	Memory
797951		sentheta	Cyberland (APIO23_cyberland)	C++17	0 / 100	235 ms	12512 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 int N = 1e5+5;
const int K = 80;

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

bool vis[N][K];

float 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-1);
	rep(i,0,n){
		adj[i].clear();
		rep(j,0,K){
			vis[i][k] = 0;
		}
	}
	
	rep(i,0,m){
		adj[mx[i]].push_back({my[i], mc[i]});
		adj[my[i]].push_back({mx[i], mc[i]});
	}
	
	float ans = 1e18;
	
	// {-moves, -dist, node}
	priority_queue<tuple<int,float,int>> pq;
	pq.push({0,0,0});
	while(!pq.empty()){
		auto[mov,dist,x] = pq.top(); pq.pop();
		mov *= -1; dist *= -1;
		if(vis[x][mov]) continue;
		vis[x][mov] = 1;
		
		if(x==tar){
			ans = min(ans, dist);
			continue;
		}
		
		if(mov < k){
			if(arr[x]==0){
				pq.push({-(mov+1), 0, x});
			}
			if(arr[x]==1){
				pq.push({-(mov+1), -dist, x});
			}
			if(arr[x]==2){
				pq.push({-(mov+1), -dist/2, x});
			}
		}
		
		for(auto[y,w] : adj[x]){
			pq.push({-mov, -(dist+w), y});
		}
	}
	
	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