Submission #797992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797992	2023-07-30T08:40:02 Z	sentheta	Cyberland (APIO23_cyberland)	C++17	100 / 100	1589 ms	62868 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	2820 KB	Correct.
2	Correct	16 ms	2788 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	3280 KB	Correct.
2	Correct	24 ms	3316 KB	Correct.
3	Correct	22 ms	3288 KB	Correct.
4	Correct	23 ms	3312 KB	Correct.
5	Correct	23 ms	3340 KB	Correct.
6	Correct	21 ms	8660 KB	Correct.
7	Correct	28 ms	8532 KB	Correct.
8	Correct	16 ms	14664 KB	Correct.
9	Correct	22 ms	2780 KB	Correct.
10	Correct	21 ms	2772 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	3372 KB	Correct.
2	Correct	29 ms	3348 KB	Correct.
3	Correct	28 ms	3360 KB	Correct.
4	Correct	27 ms	2784 KB	Correct.
5	Correct	27 ms	2784 KB	Correct.
6	Correct	9 ms	7644 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	188 ms	38264 KB	Correct.
2	Correct	217 ms	3432 KB	Correct.
3	Correct	188 ms	3300 KB	Correct.
4	Correct	201 ms	3236 KB	Correct.
5	Correct	120 ms	2760 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	3440 KB	Correct.
2	Correct	22 ms	3384 KB	Correct.
3	Correct	22 ms	3284 KB	Correct.
4	Correct	23 ms	8736 KB	Correct.
5	Correct	22 ms	2772 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	3384 KB	Correct.
2	Correct	22 ms	3412 KB	Correct.
3	Correct	51 ms	48620 KB	Correct.
4	Correct	19 ms	7252 KB	Correct.
5	Correct	23 ms	2784 KB	Correct.
6	Correct	24 ms	3364 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	244 ms	3328 KB	Correct.
2	Correct	32 ms	3796 KB	Correct.
3	Correct	600 ms	60704 KB	Correct.
4	Correct	333 ms	15960 KB	Correct.
5	Correct	756 ms	29576 KB	Correct.
6	Correct	294 ms	13772 KB	Correct.
7	Correct	326 ms	17092 KB	Correct.
8	Correct	284 ms	4812 KB	Correct.
9	Correct	191 ms	3456 KB	Correct.
10	Correct	190 ms	3336 KB	Correct.
11	Correct	274 ms	3564 KB	Correct.
12	Correct	211 ms	3412 KB	Correct.
13	Correct	221 ms	3420 KB	Correct.
14	Correct	311 ms	30968 KB	Correct.
15	Correct	304 ms	10404 KB	Correct.
16	Correct	201 ms	3312 KB	Correct.
17	Correct	269 ms	3352 KB	Correct.
18	Correct	234 ms	3476 KB	Correct.
19	Correct	623 ms	3352 KB	Correct.
20	Correct	14 ms	2644 KB	Correct.
21	Correct	17 ms	3252 KB	Correct.
22	Correct	21 ms	3796 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	508 ms	3396 KB	Correct.
2	Correct	66 ms	3796 KB	Correct.
3	Correct	531 ms	62868 KB	Correct.
4	Correct	372 ms	6648 KB	Correct.
5	Correct	1589 ms	29576 KB	Correct.
6	Correct	616 ms	13764 KB	Correct.
7	Correct	592 ms	24692 KB	Correct.
8	Correct	406 ms	3732 KB	Correct.
9	Correct	391 ms	3560 KB	Correct.
10	Correct	389 ms	3352 KB	Correct.
11	Correct	118 ms	2892 KB	Correct.
12	Correct	432 ms	3428 KB	Correct.
13	Correct	444 ms	3336 KB	Correct.
14	Correct	1328 ms	27532 KB	Correct.
15	Correct	1036 ms	32800 KB	Correct.
16	Correct	535 ms	13576 KB	Correct.
17	Correct	405 ms	4892 KB	Correct.
18	Correct	418 ms	3628 KB	Correct.
19	Correct	508 ms	3352 KB	Correct.
20	Correct	475 ms	3404 KB	Correct.
21	Correct	1328 ms	3340 KB	Correct.
22	Correct	24 ms	2756 KB	Correct.
23	Correct	32 ms	3248 KB	Correct.
24	Correct	42 ms	3860 KB	Correct.

Submission #797992

Compilation message