Submission #797991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797991	2023-07-30T08:39:20 Z	sentheta	Cyberland (APIO23_cyberland)	C++17	100 / 100	2530 ms	116940 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 long 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){
	dbg(d[node][mov]);
	dbg(dist);
	dbg(d[node][mov] <= dist);
	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;
		// dbg(abs(d[x][mov]-dist));
		// dbg(abs(d[x][mov]-dist) < E);
		if(abs(d[x][mov]-dist) > E) continue;
		
		dbg(x);
		
		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	24 ms	2772 KB	Correct.
2	Correct	24 ms	2788 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	3876 KB	Correct.
2	Correct	39 ms	3816 KB	Correct.
3	Correct	41 ms	3796 KB	Correct.
4	Correct	39 ms	3796 KB	Correct.
5	Correct	39 ms	3864 KB	Correct.
6	Correct	38 ms	14044 KB	Correct.
7	Correct	48 ms	13780 KB	Correct.
8	Correct	36 ms	25364 KB	Correct.
9	Correct	36 ms	2772 KB	Correct.
10	Correct	36 ms	2824 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	3936 KB	Correct.
2	Correct	49 ms	3884 KB	Correct.
3	Correct	46 ms	3904 KB	Correct.
4	Correct	45 ms	2832 KB	Correct.
5	Correct	45 ms	2828 KB	Correct.
6	Correct	14 ms	12184 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	299 ms	70092 KB	Correct.
2	Correct	333 ms	3928 KB	Correct.
3	Correct	305 ms	3820 KB	Correct.
4	Correct	320 ms	3876 KB	Correct.
5	Correct	214 ms	2800 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	3916 KB	Correct.
2	Correct	36 ms	3892 KB	Correct.
3	Correct	36 ms	3924 KB	Correct.
4	Correct	37 ms	14004 KB	Correct.
5	Correct	33 ms	2820 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	3916 KB	Correct.
2	Correct	37 ms	3892 KB	Correct.
3	Correct	84 ms	89520 KB	Correct.
4	Correct	32 ms	11220 KB	Correct.
5	Correct	41 ms	2820 KB	Correct.
6	Correct	40 ms	3964 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	374 ms	3956 KB	Correct.
2	Correct	48 ms	4820 KB	Correct.
3	Correct	914 ms	112132 KB	Correct.
4	Correct	527 ms	27600 KB	Correct.
5	Correct	1234 ms	51904 KB	Correct.
6	Correct	455 ms	20808 KB	Correct.
7	Correct	537 ms	30040 KB	Correct.
8	Correct	452 ms	6736 KB	Correct.
9	Correct	295 ms	3892 KB	Correct.
10	Correct	292 ms	3976 KB	Correct.
11	Correct	439 ms	4240 KB	Correct.
12	Correct	326 ms	3916 KB	Correct.
13	Correct	317 ms	4008 KB	Correct.
14	Correct	501 ms	56120 KB	Correct.
15	Correct	476 ms	17060 KB	Correct.
16	Correct	312 ms	4032 KB	Correct.
17	Correct	367 ms	3984 KB	Correct.
18	Correct	355 ms	4064 KB	Correct.
19	Correct	953 ms	3952 KB	Correct.
20	Correct	21 ms	2772 KB	Correct.
21	Correct	25 ms	3760 KB	Correct.
22	Correct	32 ms	4500 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	776 ms	4080 KB	Correct.
2	Correct	100 ms	4804 KB	Correct.
3	Correct	1160 ms	116940 KB	Correct.
4	Correct	606 ms	9976 KB	Correct.
5	Correct	2530 ms	51912 KB	Correct.
6	Correct	952 ms	22364 KB	Correct.
7	Correct	919 ms	46128 KB	Correct.
8	Correct	648 ms	6380 KB	Correct.
9	Correct	606 ms	4940 KB	Correct.
10	Correct	595 ms	5004 KB	Correct.
11	Correct	274 ms	3916 KB	Correct.
12	Correct	670 ms	5068 KB	Correct.
13	Correct	656 ms	4884 KB	Correct.
14	Correct	2071 ms	50140 KB	Correct.
15	Correct	1751 ms	61648 KB	Correct.
16	Correct	844 ms	25160 KB	Correct.
17	Correct	643 ms	8780 KB	Correct.
18	Correct	636 ms	4852 KB	Correct.
19	Correct	786 ms	5024 KB	Correct.
20	Correct	729 ms	5008 KB	Correct.
21	Correct	2019 ms	5852 KB	Correct.
22	Correct	39 ms	2772 KB	Correct.
23	Correct	49 ms	3812 KB	Correct.
24	Correct	64 ms	4756 KB	Correct.

Submission #797991

Compilation message