Submission #759650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
759650	2023-06-16T13:55:13 Z	IvanJ	Cyberland (APIO23_cyberland)	C++17	100 / 100	2452 ms	20656 KB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const double inf = 1e18;
double dist[maxn], dist1[maxn];
vector<ii> adj[maxn];
int vis[maxn], change[maxn];
int X;

void reach(int x) {
	if(vis[x] || x == X) return;
	vis[x] = 1;
	for(auto p : adj[x]) 
		reach(p.x);
}

double solve(int N, int M, int K, int H, vector<int> u, vector<int> v, vector<int> c, vector<int> arr) {
	for(int i = 0;i < N;i++) {
		adj[i].clear();
		vis[i] = 0;
		dist[i] = inf;
	}
	
	for(int i = 0;i < M;i++) 
		adj[u[i]].pb({v[i], c[i]}), adj[v[i]].pb({u[i], c[i]});
	
	X = H;
	reach(0);
	for(int i = 0;i < N;i++) 
		if(arr[i] == 0 && vis[i] == 1) dist[i] = 0;
	dist[0] = 0;
	
	for(int k = 0;k <= K;k++) {
		set<pair<double, int>> s;
		for(int i = 0;i < N;i++) {
			change[i] = 0;
			dist1[i] = dist[i];
			if(vis[i] == 1) s.insert({dist[i], i});
		}
		
		int flag = 0;
		while(s.size()) {
			auto state = *s.begin();
			s.erase(state);
			int x = state.y;
			if(x == H) continue;
			
			for(auto p : adj[x]) {
				int y = p.x;
				double cost = p.y;
				
				if(arr[y] == 1) {
					if(dist1[x] + cost < dist1[y]) {
						s.erase({dist1[y], y});
						dist1[y] = dist1[x] + cost;
						dist[y] = dist1[y], flag = 1;
						s.insert({dist1[y], y});
					}
				} 
				if(arr[y] == 2) {
					if(dist1[x] + cost < dist1[y]) {
						s.erase({dist1[y], y});
						dist1[y] = dist1[x] + cost;
						s.insert({dist1[y], y});
					}
					if((dist1[x] + cost) / 2.0 < dist[y]) 
						dist[y] = (dist1[x] + cost) / 2.0, flag = 1;
				}
			}
		}
		if(flag == 0) break;
	}
	
	if(dist[H] == inf) return -1;
	return dist[H]; 
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2844 KB	Correct.
2	Correct	15 ms	2812 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	2876 KB	Correct.
2	Correct	44 ms	2892 KB	Correct.
3	Correct	50 ms	2872 KB	Correct.
4	Correct	53 ms	2860 KB	Correct.
5	Correct	44 ms	2832 KB	Correct.
6	Correct	43 ms	4112 KB	Correct.
7	Correct	57 ms	4160 KB	Correct.
8	Correct	25 ms	5588 KB	Correct.
9	Correct	35 ms	2732 KB	Correct.
10	Correct	35 ms	2732 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	2848 KB	Correct.
2	Correct	41 ms	2848 KB	Correct.
3	Correct	37 ms	2876 KB	Correct.
4	Correct	36 ms	2732 KB	Correct.
5	Correct	37 ms	2752 KB	Correct.
6	Correct	9 ms	3816 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	143 ms	9008 KB	Correct.
2	Correct	159 ms	2868 KB	Correct.
3	Correct	135 ms	2860 KB	Correct.
4	Correct	149 ms	2852 KB	Correct.
5	Correct	108 ms	2728 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2852 KB	Correct.
2	Correct	28 ms	2896 KB	Correct.
3	Correct	29 ms	2900 KB	Correct.
4	Correct	30 ms	3940 KB	Correct.
5	Correct	24 ms	2644 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2900 KB	Correct.
2	Correct	24 ms	2900 KB	Correct.
3	Correct	32 ms	9500 KB	Correct.
4	Correct	18 ms	3884 KB	Correct.
5	Correct	27 ms	2644 KB	Correct.
6	Correct	27 ms	2916 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	2852 KB	Correct.
2	Correct	19 ms	2900 KB	Correct.
3	Correct	1331 ms	17608 KB	Correct.
4	Correct	667 ms	6040 KB	Correct.
5	Correct	477 ms	10912 KB	Correct.
6	Correct	157 ms	7536 KB	Correct.
7	Correct	623 ms	6388 KB	Correct.
8	Correct	473 ms	3264 KB	Correct.
9	Correct	112 ms	2892 KB	Correct.
10	Correct	116 ms	2916 KB	Correct.
11	Correct	403 ms	3192 KB	Correct.
12	Correct	138 ms	2840 KB	Correct.
13	Correct	122 ms	2852 KB	Correct.
14	Correct	538 ms	10188 KB	Correct.
15	Correct	508 ms	4680 KB	Correct.
16	Correct	120 ms	2912 KB	Correct.
17	Correct	149 ms	2880 KB	Correct.
18	Correct	138 ms	2828 KB	Correct.
19	Correct	458 ms	2852 KB	Correct.
20	Correct	10 ms	2644 KB	Correct.
21	Correct	11 ms	2772 KB	Correct.
22	Correct	13 ms	3156 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	247 ms	2852 KB	Correct.
2	Correct	34 ms	2912 KB	Correct.
3	Correct	2175 ms	20656 KB	Correct.
4	Correct	672 ms	3772 KB	Correct.
5	Correct	893 ms	10848 KB	Correct.
6	Correct	303 ms	7628 KB	Correct.
7	Correct	955 ms	8924 KB	Correct.
8	Correct	606 ms	3100 KB	Correct.
9	Correct	195 ms	2948 KB	Correct.
10	Correct	198 ms	2824 KB	Correct.
11	Correct	336 ms	2832 KB	Correct.
12	Correct	223 ms	2892 KB	Correct.
13	Correct	225 ms	2932 KB	Correct.
14	Correct	1854 ms	10336 KB	Correct.
15	Correct	2452 ms	10432 KB	Correct.
16	Correct	1036 ms	5572 KB	Correct.
17	Correct	704 ms	3280 KB	Correct.
18	Correct	199 ms	2920 KB	Correct.
19	Correct	257 ms	2864 KB	Correct.
20	Correct	241 ms	2904 KB	Correct.
21	Correct	843 ms	2964 KB	Correct.
22	Correct	11 ms	2644 KB	Correct.
23	Correct	17 ms	2772 KB	Correct.
24	Correct	27 ms	3156 KB	Correct.

Submission #759650

Compilation message