oj.uz

답안 #797992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797992 2023-07-30T08:40:02 Z sentheta 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1589 ms 62868 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2820 KB Correct.
2 Correct 16 ms 2788 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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.