oj.uz

Submission #1088960

# Submission time Handle Problem Language Result Execution time Memory
1088960 2024-09-15T16:12:54 Z Math4Life2020 Cyberland (APIO23_cyberland) C++17
68 / 100
 3000 ms 2097152 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
using namespace std;
using ll = int; using pii = pair<ll,ll>;
using ld = 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];
	ld tminT[N][K+1]; //temporary
	bool dfsf[N];
	for (ll i=0;i<N;i++) {
		dfsf[i]=0;
		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]});
	}
	stack<int> s;
	s.push(0);
	while (!s.empty()) {
		ll x0 = s.top(); s.pop();
		if (!dfsf[x0]) {
			dfsf[x0]=1;
			if (x0==H) {
				continue;
			}
			for (pii p0: adj[x0]) {
				s.push(p0.first);
			}
		}
	}
	if (!dfsf[H]) {
		return -1.0;
	}
	priority_queue<pair<ld,ll>> pq[K+1]; //{#k,{time,position}}
	pq[0].push({0.0,0});
	for (ll i=0;i<N;i++) {
		if (dfsf[i] && (arr[i]==0)) {
			pq[0].push({0.0,i});
		}
	}
	for (ll k=0;k<=K;k++) {
		if (k != 0) {
			for (ll i=0;i<N;i++) {
				if (tmin[i][k]!=INF) {
					pq[k].push({tmin[i][k],i});
				}
			}
		}
		while (!pq[k].empty()) {
			auto A = pq[k].top(); pq[k].pop();
			ld T = A.first; ll x0 = A.second;
			if (arr[x0]==0 && T != 0.0) {
				continue;
			}
			if (tmin[x0][k]<T) {
				continue;
			}
			tmin[x0][k]=T;
			if (x0==H) {
				continue;
			}
			for (pii p0: adj[x0]) {
				ll y0 = p0.first; ld ce = p0.second;
				if (tmin[y0][k]>=(ce+T+1e-10)) {
					pq[k].push({ce+T,y0});
					tmin[y0][k]=ce+T;
				}
				if (arr[x0]==2 && k<K) {
					tmin[y0][k+1]=min(tmin[y0][k+1],ce+T/2);
				}
			}
		}
	}
	ld ans = INF;
	for (ll k=0;k<=K;k++) {
		ans = min(ans,tmin[H][k]);
	}
	return ans;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, vi, vi, vi, vi)':
cyberland.cpp:12:5: warning: unused variable 'tminT' [-Wunused-variable]
   12 |  ld tminT[N][K+1]; //temporary
      |     ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Correct.
2 Correct 15 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 604 KB Correct.
2 Correct 20 ms 848 KB Correct.
3 Correct 21 ms 604 KB Correct.
4 Correct 21 ms 604 KB Correct.
5 Correct 21 ms 604 KB Correct.
6 Correct 22 ms 3672 KB Correct.
7 Correct 23 ms 3588 KB Correct.
8 Correct 12 ms 7004 KB Correct.
9 Correct 18 ms 512 KB Correct.
10 Correct 18 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 604 KB Correct.
2 Correct 30 ms 600 KB Correct.
3 Correct 32 ms 860 KB Correct.
4 Correct 23 ms 344 KB Correct.
5 Correct 22 ms 344 KB Correct.
6 Correct 7 ms 3164 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 23120 KB Correct.
2 Correct 60 ms 1024 KB Correct.
3 Correct 55 ms 1072 KB Correct.
4 Correct 55 ms 1096 KB Correct.
5 Correct 44 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 600 KB Correct.
2 Correct 94 ms 600 KB Correct.
3 Correct 98 ms 808 KB Correct.
4 Correct 933 ms 3656 KB Correct.
5 Correct 18 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 604 KB Correct.
2 Correct 24 ms 788 KB Correct.
3 Correct 53 ms 25684 KB Correct.
4 Correct 67 ms 2904 KB Correct.
5 Correct 21 ms 348 KB Correct.
6 Correct 28 ms 808 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1028 KB Correct.
2 Correct 24 ms 1372 KB Correct.
3 Execution timed out 3072 ms 24808 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

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