Submission #847763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
847763	2023-09-10T10:44:15 Z	KN200711	Cyberland (APIO23_cyberland)	C++17	100 / 100	1460 ms	69624 KB

cyberland

#include "cyberland.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

bool vis[100001];
vector< pair<int, double> > edge[100001];
int h1;

void dfs(int a) {
	vis[a] = 1;
	if(a == h1) return;
	for(auto p : edge[a]) {
		if(!vis[p.fi]) dfs(p.fi);
	}
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	K = min(K, 70);
	h1 = H;
	for(int i=0;i<N;i++) {
		vis[i] = 0;
		edge[i].clear();
	}
	for(int i=0;i<M;i++) {
		edge[x[i]].push_back(make_pair(y[i], (double) c[i]));
		edge[y[i]].push_back(make_pair(x[i], (double) c[i]));
	}
	dfs(0);
	
	vector< vector<double> > dp;
	dp.resize(K + 1);
	for(int i=0;i<=K;i++) {
		dp[i].resize(N);
		for(int c=0;c<N;c++) dp[i][c] = -1;
	}
	priority_queue< pair<int, pair<double, int> > > PQ;
	for(int d=0;d<N;d++) {
		if(d == 0 || (arr[d] == 0 && vis[d])) PQ.push(make_pair(0, make_pair(0, d)));
	}
	
	while(!PQ.empty()) {
		double a = PQ.top().se.fi;
		int nm = -PQ.top().fi, pos = PQ.top().se.se;
		PQ.pop();
		
		if(dp[nm][pos] != -1) continue;
		dp[nm][pos] = -a;
	//	cout<<pos<<" "<<-nm<<" "<<-a<<endl;
		if(pos == H) continue;
		
		for(auto p : edge[pos]) {
			if(arr[p.fi] == 0) continue;
			else if(arr[p.fi] == 1 && dp[nm][p.fi] == -1) PQ.push(make_pair(-nm, make_pair((double) a - ((double) p.se), p.fi)));
			else if(arr[p.fi] == 2) {
				if(nm + 1 <= K && dp[nm+1][p.fi] == -1) PQ.push(make_pair(-nm-1, make_pair(((double) a - (double) p.se) / ((double) 2), p.fi)));
				if(dp[nm][p.fi] == -1) PQ.push(make_pair(-nm, make_pair(((double) a - (double) p.se), p.fi)));
			} 
		}
	}
	double ans = 1e18;
	for(int v=0;v<=K;v++) {
		if(dp[v][H] != (double) -1) ans = min(ans, dp[v][H]);
	}
	if(ans == 1e18) ans = -1;
	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2904 KB	Correct.
2	Correct	25 ms	2904 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	3160 KB	Correct.
2	Correct	23 ms	3192 KB	Correct.
3	Correct	21 ms	3160 KB	Correct.
4	Correct	23 ms	3200 KB	Correct.
5	Correct	22 ms	3200 KB	Correct.
6	Correct	25 ms	6176 KB	Correct.
7	Correct	27 ms	6060 KB	Correct.
8	Correct	13 ms	9304 KB	Correct.
9	Correct	22 ms	2904 KB	Correct.
10	Correct	22 ms	3004 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	3184 KB	Correct.
2	Correct	26 ms	3204 KB	Correct.
3	Correct	22 ms	3252 KB	Correct.
4	Correct	25 ms	2904 KB	Correct.
5	Correct	25 ms	2904 KB	Correct.
6	Correct	6 ms	5468 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	22348 KB	Correct.
2	Correct	111 ms	3332 KB	Correct.
3	Correct	94 ms	4184 KB	Correct.
4	Correct	100 ms	4136 KB	Correct.
5	Correct	67 ms	3664 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3320 KB	Correct.
2	Correct	24 ms	3316 KB	Correct.
3	Correct	23 ms	3292 KB	Correct.
4	Correct	24 ms	6132 KB	Correct.
5	Correct	20 ms	2904 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3300 KB	Correct.
2	Correct	20 ms	3552 KB	Correct.
3	Correct	40 ms	27740 KB	Correct.
4	Correct	16 ms	5456 KB	Correct.
5	Correct	22 ms	2904 KB	Correct.
6	Correct	22 ms	3284 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	3732 KB	Correct.
2	Correct	26 ms	3160 KB	Correct.
3	Correct	406 ms	24848 KB	Correct.
4	Correct	248 ms	11272 KB	Correct.
5	Correct	539 ms	24100 KB	Correct.
6	Correct	458 ms	16832 KB	Correct.
7	Correct	288 ms	9620 KB	Correct.
8	Correct	213 ms	5564 KB	Correct.
9	Correct	157 ms	4324 KB	Correct.
10	Correct	141 ms	4652 KB	Correct.
11	Correct	198 ms	4964 KB	Correct.
12	Correct	142 ms	4296 KB	Correct.
13	Correct	155 ms	4276 KB	Correct.
14	Correct	255 ms	12064 KB	Correct.
15	Correct	246 ms	7188 KB	Correct.
16	Correct	149 ms	4368 KB	Correct.
17	Correct	166 ms	4428 KB	Correct.
18	Correct	184 ms	4284 KB	Correct.
19	Correct	350 ms	5308 KB	Correct.
20	Correct	11 ms	2908 KB	Correct.
21	Correct	11 ms	3076 KB	Correct.
22	Correct	42 ms	4276 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	381 ms	3772 KB	Correct.
2	Correct	57 ms	3672 KB	Correct.
3	Correct	262 ms	69624 KB	Correct.
4	Correct	314 ms	5592 KB	Correct.
5	Correct	1170 ms	35268 KB	Correct.
6	Correct	995 ms	19140 KB	Correct.
7	Correct	554 ms	15952 KB	Correct.
8	Correct	298 ms	5408 KB	Correct.
9	Correct	315 ms	4612 KB	Correct.
10	Correct	305 ms	4540 KB	Correct.
11	Correct	225 ms	3920 KB	Correct.
12	Correct	302 ms	4624 KB	Correct.
13	Correct	331 ms	4608 KB	Correct.
14	Correct	1460 ms	32080 KB	Correct.
15	Correct	847 ms	37028 KB	Correct.
16	Correct	454 ms	15632 KB	Correct.
17	Correct	315 ms	6780 KB	Correct.
18	Correct	315 ms	4692 KB	Correct.
19	Correct	347 ms	4700 KB	Correct.
20	Correct	352 ms	4740 KB	Correct.
21	Correct	712 ms	5824 KB	Correct.
22	Correct	19 ms	2904 KB	Correct.
23	Correct	23 ms	3352 KB	Correct.
24	Correct	92 ms	4632 KB	Correct.

Submission #847763

Compilation message