oj.uz

Submission #1088939

# Submission time Handle Problem Language Result Execution time Memory
1088939 2024-09-15T14:59:18 Z Math4Life2020 Cyberland (APIO23_cyberland) C++17
42 / 100
 3000 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ld = long double; using vi = vector<int>;

const ld INF = 1e18;

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
	ld tmin[N][K+1];
	for (ll i=0;i<N;i++) {
		for (ll k=0;k<=K;k++) {
			tmin[i][k]=INF;
		}
	}
	vector<pii> adj[N]; //vertex,cost
	for (ll i=0;i<M;i++) {
		adj[x[i]].push_back({y[i],c[i]});
		adj[y[i]].push_back({x[i],c[i]});
	}
	priority_queue<pair<ld,pii>> pq; //{time,{position, #k}}
	pq.push({0.0,{0,0}});
	while (!pq.empty()) {
		auto A = pq.top(); pq.pop();
		ld T = A.first; ll x = A.second.first; ll k = A.second.second;
		if (arr[x]==0) {
			T = 0.0; k = 0;
		}
		if (tmin[x][k]<=(T+1e-10)) {
			continue;
		}
		tmin[x][k]=min(tmin[x][k],T);
		if (x==H) {
			continue;
		}
		for (pii p0: adj[x]) {
			ll y = p0.first; ld ce = p0.second;
			pq.push({ce+T,{y,k}});
			if (arr[x]==2 && k<K) {
				pq.push({ce+T/2,{y,k+1}});
			}
		}
	}
	ld ans = INF;
	for (ll k=0;k<=K;k++) {
		ans = min(ans,tmin[H][k]);
	}
	if (ans == INF) {
		return -1.0;
	} else {
		return ans;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 856 KB Correct.
2 Correct 26 ms 852 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1880 KB Correct.
2 Correct 33 ms 1880 KB Correct.
3 Correct 37 ms 1940 KB Correct.
4 Correct 35 ms 1884 KB Correct.
5 Correct 35 ms 1884 KB Correct.
6 Correct 33 ms 7004 KB Correct.
7 Correct 39 ms 7116 KB Correct.
8 Correct 19 ms 12376 KB Correct.
9 Correct 30 ms 1412 KB Correct.
10 Correct 29 ms 1364 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1876 KB Correct.
2 Correct 47 ms 1876 KB Correct.
3 Correct 45 ms 1832 KB Correct.
4 Correct 37 ms 1364 KB Correct.
5 Correct 37 ms 1428 KB Correct.
6 Correct 11 ms 5208 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 40132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 1876 KB Correct.
2 Correct 1917 ms 2008 KB Correct.
3 Correct 1998 ms 2124 KB Correct.
4 Execution timed out 3044 ms 4572 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1984 KB Correct.
2 Correct 227 ms 1900 KB Correct.
3 Correct 66 ms 47188 KB Correct.
4 Correct 741 ms 5620 KB Correct.
5 Correct 52 ms 1276 KB Correct.
6 Correct 188 ms 2120 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3006 ms 132244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 974 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -