Submission #939999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939999	2024-03-07T03:37:48 Z	tamir1	Cyberland (APIO23_cyberland)	C++17	100 / 100	1875 ms	74392 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
#define ff first
#define ss second
#define ll long long
const double INF=1e18;
using namespace std;
ll h,i,j;
vector<pair<ll,double>> v[200001];
bitset<200005> vis;
priority_queue<pair<double,ll>> q;
double dp[200001][71],dist;
void dfs(ll a){
	if(a==h) return;
	if(vis[a]) return;
	vis[a]=1;
	for(pair<ll,double> l:v[a]){
		dfs(l.ff);
	}
}
void dijkstra(ll t){
	while(!q.empty()){
		ll a=q.top().ss;
		double d=q.top().ff;
		q.pop();
		if(dp[a][t]!=-1) continue;
		dp[a][t]=-d;
		if(a!=h) for(pair<ll,double> l:v[a]){
			if(dp[l.ff][t]==-1) q.push({d-l.ss,l.ff});
		}
	}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	h=H;
	dist=INF;
	K=min(K,70);
	for(i=0;i<M;i++){
		v[x[i]].push_back({y[i],c[i]});
		v[y[i]].push_back({x[i],c[i]});
	}
	dfs(0);
	q.push({0,0});
	for(i=0;i<N;i++){
		if(vis[i]==1 && arr[i]==0) q.push({0,i});
		for(j=0;j<=K;j++){
			dp[i][j]=-1;
		}
	}
	dijkstra(0);
	for(j=1;j<=K;j++){
		for(i=0;i<N;i++){
			if(vis[i]==1 && arr[i]==2){
				for(pair<ll,double> l:v[i])
				q.push({-1*(dp[i][j-1]/2)-l.ss,l.ff});
			}
		}
		dijkstra(j);
	}
	vis.reset();
	for(i=0;i<N;i++){
		v[i].clear();
	}
	for(j=0;j<=K;j++){
		if(dp[H][j]!=-1) dist=min(dist,dp[H][j]);
	}
	return (dist==INF ? -1 : dist);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	5724 KB	Correct.
2	Correct	20 ms	5708 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	8536 KB	Correct.
2	Correct	25 ms	8660 KB	Correct.
3	Correct	24 ms	8540 KB	Correct.
4	Correct	24 ms	8756 KB	Correct.
5	Correct	25 ms	8792 KB	Correct.
6	Correct	27 ms	13396 KB	Correct.
7	Correct	29 ms	13656 KB	Correct.
8	Correct	15 ms	19800 KB	Correct.
9	Correct	22 ms	6236 KB	Correct.
10	Correct	23 ms	6344 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	8792 KB	Correct.
2	Correct	27 ms	8536 KB	Correct.
3	Correct	31 ms	8536 KB	Correct.
4	Correct	26 ms	6228 KB	Correct.
5	Correct	26 ms	6236 KB	Correct.
6	Correct	11 ms	12888 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	45020 KB	Correct.
2	Correct	144 ms	8528 KB	Correct.
3	Correct	121 ms	8616 KB	Correct.
4	Correct	131 ms	8528 KB	Correct.
5	Correct	67 ms	6740 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	8592 KB	Correct.
2	Correct	25 ms	8784 KB	Correct.
3	Correct	30 ms	8804 KB	Correct.
4	Correct	26 ms	14172 KB	Correct.
5	Correct	21 ms	6236 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	8708 KB	Correct.
2	Correct	23 ms	8536 KB	Correct.
3	Correct	45 ms	56916 KB	Correct.
4	Correct	18 ms	11352 KB	Correct.
5	Correct	24 ms	6236 KB	Correct.
6	Correct	29 ms	8796 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	8844 KB	Correct.
2	Correct	41 ms	8016 KB	Correct.
3	Correct	532 ms	68688 KB	Correct.
4	Correct	230 ms	22288 KB	Correct.
5	Correct	850 ms	36740 KB	Correct.
6	Correct	684 ms	21192 KB	Correct.
7	Correct	267 ms	24144 KB	Correct.
8	Correct	184 ms	10012 KB	Correct.
9	Correct	209 ms	8784 KB	Correct.
10	Correct	200 ms	8648 KB	Correct.
11	Correct	166 ms	9564 KB	Correct.
12	Correct	208 ms	8724 KB	Correct.
13	Correct	226 ms	8788 KB	Correct.
14	Correct	260 ms	38304 KB	Correct.
15	Correct	215 ms	17044 KB	Correct.
16	Correct	217 ms	8788 KB	Correct.
17	Correct	259 ms	8788 KB	Correct.
18	Correct	233 ms	8712 KB	Correct.
19	Correct	501 ms	9784 KB	Correct.
20	Correct	11 ms	5468 KB	Correct.
21	Correct	18 ms	7516 KB	Correct.
22	Correct	66 ms	8792 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	8796 KB	Correct.
2	Correct	89 ms	7992 KB	Correct.
3	Correct	236 ms	74392 KB	Correct.
4	Correct	261 ms	12372 KB	Correct.
5	Correct	1875 ms	36804 KB	Correct.
6	Correct	1551 ms	21196 KB	Correct.
7	Correct	483 ms	32336 KB	Correct.
8	Correct	220 ms	9720 KB	Correct.
9	Correct	435 ms	8788 KB	Correct.
10	Correct	411 ms	8828 KB	Correct.
11	Correct	161 ms	6636 KB	Correct.
12	Correct	449 ms	8720 KB	Correct.
13	Correct	473 ms	8744 KB	Correct.
14	Correct	1435 ms	36264 KB	Correct.
15	Correct	816 ms	40732 KB	Correct.
16	Correct	434 ms	20048 KB	Correct.
17	Correct	249 ms	9812 KB	Correct.
18	Correct	471 ms	8888 KB	Correct.
19	Correct	521 ms	8840 KB	Correct.
20	Correct	510 ms	8812 KB	Correct.
21	Correct	1129 ms	9644 KB	Correct.
22	Correct	18 ms	5516 KB	Correct.
23	Correct	37 ms	7516 KB	Correct.
24	Correct	143 ms	8796 KB	Correct.

Submission #939999

Compilation message