oj.uz

Submission #841015

# Submission time Handle Problem Language Result Execution time Memory
841015 2023-09-01T04:51:03 Z GoldLight Cyberland (APIO23_cyberland) C++17
100 / 100
 1156 ms 67704 KB 
#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

const int N=1e5;
const double INF=1e16;
vector<pair<int,int>> v[N+1];
priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>>> pq;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a){
	for(int i=0; i<n; i++) v[i].clear();
	for(int i=0; i<m; i++){
		v[x[i]].push_back({y[i], c[i]});
		v[y[i]].push_back({x[i], c[i]});
	}
	k=min(k, 70);
	set<int> t;
	vector<bool> vis(n);
	queue<int> q;
	q.push(0);
	vis[0]=true;
	while(!q.empty()){
		int u=q.front(); q.pop();
		if(u==h) continue;
		for(auto [p, q1]:v[u]){
			if(vis[p]) continue;
			if(a[p]==0) t.insert(p);
			q.push(p);
			vis[p]=true;
		}
	}
	double pw[k+1];
	pw[0]=1.0;
	for(int i=1; i<=k; i++) pw[i]=pw[i-1]*2;
	vector<vector<double>> dp(n, vector<double>(k+1, INF));
	for(int i=0; i<=k; i++) dp[h][i]=0;
	pq.push({0, h, 0});
	double ans=INF;
	while(!pq.empty()){
		auto[d, u, dis]=pq.top(); pq.pop();
		if(d>dp[u][dis]) continue;
		if(t.count(u)){
			ans=min(ans, d);
			continue;
		}
		for(auto [to, dist]:v[u]){
			if(d+dist/pw[dis]<dp[to][dis]){
				dp[to][dis]=d+dist/pw[dis];
				pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2))});
			}
		}
	}
	for(int i=0; i<=k; i++) ans=min(ans, dp[0][i]);
	if(ans==INF) return -1;
	return ans;
}
/*
int main(){
	fast();
	int n, m, k, h; cin>>n>>m>>k>>h;
	vector<int> x(N+1), y(N+1), c(N+1), a(N+1); 
	for(int i=0; i<m; i++){
		cin>>x[i]>>y[i]>>c[i];
	}
	for(int i=0; i<n; i++) cin>>a[i];
	cout<<solve(n, m, k, h, x, y, c, a);
}
*/
/*
const int N=1e5;
const double INF=1e16;
int n, m, k, h;
vector<pair<int,int>> v[N+1], ad; //adventure graph
vector<int> a;
bool f=false; //find cyberland
void dfs(int node, int p){
	if(f) return;
	for(auto [i, d]:v[node]){
		if(i==p) continue;
		int di=0;
		if(a[i]!=0) di=d;
		ad.push_back({di, a[i]});
		if(i==h) f=true;
		dfs(i, node);
	}
	if(f) return;
	ad.pop_back();
}
priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>>> pq;
double solve(int nn, int mm, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> aa){
	for(int i=0; i<n; i++) v[i].clear();
	n=nn, m=mm, k=kk, h=hh, a=aa;
	for(int i=0; i<m; i++){
		v[x[i]].push_back({y[i], c[i]});
		v[y[i]].push_back({x[i], c[i]});
	}
	// if(m==n-1){
	// 	ad.clear();
	// 	dfs(0, -1);
	// 	priority_queue<int> pqq;
	// 	double ans=0;
	// 	for(auto [p, q]:ad){
	// 		if(q==2) pqq.push(p);
	// 		else ans+=p;
	// 	}
	// 	while(!pqq.empty()){
	// 		int u=pqq.top(); pqq.pop();
	// 		if(k) ans+=double(u)/2;
	// 		else ans+=u;
	// 		k--;
	// 	}
	// 	return ans;
	// }
	vector<vector<double>> dp(n+1, vector<double>(k+1, INF));
	dp[0][0]=0;
	pq.push({0, 0, 0}); //dist, node now, disc
	while(!pq.empty()){
		auto[d, u, dis]=pq.top(); pq.pop();
		if(d>dp[u][dis]) continue;
		for(auto [to, dist]:v[u]){
			if(a[to]==0){
				if(0<dp[to][dis]){
					dp[to][dis]=0;
					pq.push({0, to, dis});
				}
			}
			else if(a[to]==1){
				if(d+dist<dp[to][dis]){
					dp[to][dis]=d+dist;
					pq.push({dp[to][dis], to, dis});
				}
			}
			else{
				if(d+dist<dp[to][dis]){
					dp[to][dis]=d+dist;
					pq.push({dp[to][dis], to, dis});
				}
				if(dis<k && d+dist/2<dp[to][dis+1]){
					dp[to][dis+1]=d+dist/2;
					pq.push({dp[to][dis+1], to, dis+1});
				}
			}
		}
	}
	double ans=INF;
	for(int i=0; i<=k; i++) ans=min(ans, dp[h][i]);
	if(ans==INF) return -1;
	else return ans;
}
*/
/*
int main(){
	fast();
	int n, m, k, h; cin>>n>>m>>k>>h;
	vector<int> x(N+1), y(N+1), c(N+1), a(N+1); 
	for(int i=0; i<m; i++){
		cin>>x[i]>>y[i]>>c[i];
	}
	for(int i=0; i<n; i++) cin>>a[i];
	cout<<solve(n, m, k, h, x, y, c, a);
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2772 KB Correct.
2 Correct 19 ms 2804 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3020 KB Correct.
2 Correct 23 ms 3052 KB Correct.
3 Correct 22 ms 3036 KB Correct.
4 Correct 23 ms 3052 KB Correct.
5 Correct 23 ms 3076 KB Correct.
6 Correct 22 ms 6176 KB Correct.
7 Correct 27 ms 5904 KB Correct.
8 Correct 14 ms 9428 KB Correct.
9 Correct 21 ms 2644 KB Correct.
10 Correct 21 ms 2756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3028 KB Correct.
2 Correct 21 ms 3044 KB Correct.
3 Correct 22 ms 3084 KB Correct.
4 Correct 25 ms 2644 KB Correct.
5 Correct 23 ms 2748 KB Correct.
6 Correct 7 ms 5588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22488 KB Correct.
2 Correct 23 ms 3016 KB Correct.
3 Correct 22 ms 3060 KB Correct.
4 Correct 23 ms 3032 KB Correct.
5 Correct 41 ms 2756 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3100 KB Correct.
2 Correct 24 ms 3088 KB Correct.
3 Correct 21 ms 3108 KB Correct.
4 Correct 22 ms 5948 KB Correct.
5 Correct 19 ms 2752 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3084 KB Correct.
2 Correct 18 ms 3124 KB Correct.
3 Correct 44 ms 28460 KB Correct.
4 Correct 17 ms 4932 KB Correct.
5 Correct 22 ms 2760 KB Correct.
6 Correct 21 ms 3228 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3100 KB Correct.
2 Correct 13 ms 3156 KB Correct.
3 Correct 588 ms 26352 KB Correct.
4 Correct 187 ms 8804 KB Correct.
5 Correct 285 ms 17732 KB Correct.
6 Correct 137 ms 9736 KB Correct.
7 Correct 250 ms 8612 KB Correct.
8 Correct 113 ms 3824 KB Correct.
9 Correct 55 ms 3180 KB Correct.
10 Correct 53 ms 3188 KB Correct.
11 Correct 87 ms 3104 KB Correct.
12 Correct 60 ms 3136 KB Correct.
13 Correct 58 ms 3140 KB Correct.
14 Correct 243 ms 9872 KB Correct.
15 Correct 229 ms 4916 KB Correct.
16 Correct 62 ms 3084 KB Correct.
17 Correct 66 ms 3204 KB Correct.
18 Correct 56 ms 3100 KB Correct.
19 Correct 82 ms 3068 KB Correct.
20 Correct 7 ms 2744 KB Correct.
21 Correct 7 ms 2900 KB Correct.
22 Correct 11 ms 3412 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3520 KB Correct.
2 Correct 28 ms 3796 KB Correct.
3 Correct 504 ms 67704 KB Correct.
4 Correct 271 ms 7004 KB Correct.
5 Correct 658 ms 34508 KB Correct.
6 Correct 302 ms 16212 KB Correct.
7 Correct 469 ms 16620 KB Correct.
8 Correct 127 ms 5300 KB Correct.
9 Correct 124 ms 4448 KB Correct.
10 Correct 110 ms 4324 KB Correct.
11 Correct 111 ms 3956 KB Correct.
12 Correct 131 ms 4540 KB Correct.
13 Correct 122 ms 4592 KB Correct.
14 Correct 1156 ms 30532 KB Correct.
15 Correct 1101 ms 37052 KB Correct.
16 Correct 447 ms 15600 KB Correct.
17 Correct 173 ms 6704 KB Correct.
18 Correct 134 ms 4512 KB Correct.
19 Correct 135 ms 4544 KB Correct.
20 Correct 118 ms 4432 KB Correct.
21 Correct 179 ms 5376 KB Correct.
22 Correct 13 ms 2772 KB Correct.
23 Correct 14 ms 3332 KB Correct.
24 Correct 21 ms 4180 KB Correct.