oj.uz

Submission #841014

# Submission time Handle Problem Language Result Execution time Memory
841014 2023-09-01T04:50:18 Z GoldLight Cyberland (APIO23_cyberland) C++17
97 / 100
 569 ms 62336 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, 60);
	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 18 ms 2772 KB Correct.
2 Correct 19 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3084 KB Correct.
2 Correct 23 ms 2996 KB Correct.
3 Correct 23 ms 3028 KB Correct.
4 Correct 24 ms 2988 KB Correct.
5 Correct 23 ms 3072 KB Correct.
6 Correct 23 ms 6056 KB Correct.
7 Correct 27 ms 5996 KB Correct.
8 Correct 16 ms 9428 KB Correct.
9 Correct 22 ms 2764 KB Correct.
10 Correct 24 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3052 KB Correct.
2 Correct 21 ms 3028 KB Correct.
3 Correct 21 ms 3100 KB Correct.
4 Correct 28 ms 2644 KB Correct.
5 Correct 22 ms 2644 KB Correct.
6 Correct 6 ms 5588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 22484 KB Correct.
2 Correct 22 ms 3036 KB Correct.
3 Correct 22 ms 3048 KB Correct.
4 Correct 23 ms 3056 KB Correct.
5 Correct 41 ms 2644 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3088 KB Correct.
2 Correct 22 ms 3084 KB Correct.
3 Correct 21 ms 3104 KB Correct.
4 Correct 23 ms 5972 KB Correct.
5 Correct 19 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3088 KB Correct.
2 Correct 18 ms 3060 KB Correct.
3 Correct 43 ms 28460 KB Correct.
4 Correct 16 ms 4936 KB Correct.
5 Correct 21 ms 2644 KB Correct.
6 Correct 24 ms 3112 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3132 KB Correct.
2 Correct 13 ms 3156 KB Correct.
3 Correct 569 ms 26352 KB Correct.
4 Correct 198 ms 8868 KB Correct.
5 Correct 273 ms 17740 KB Correct.
6 Correct 132 ms 9740 KB Correct.
7 Correct 247 ms 8512 KB Correct.
8 Correct 118 ms 3704 KB Correct.
9 Correct 55 ms 3172 KB Correct.
10 Correct 52 ms 3136 KB Correct.
11 Correct 93 ms 3144 KB Correct.
12 Correct 60 ms 3144 KB Correct.
13 Correct 57 ms 3132 KB Correct.
14 Correct 234 ms 9884 KB Correct.
15 Correct 217 ms 4992 KB Correct.
16 Correct 62 ms 3116 KB Correct.
17 Correct 64 ms 3072 KB Correct.
18 Correct 58 ms 3096 KB Correct.
19 Correct 83 ms 3048 KB Correct.
20 Correct 7 ms 2644 KB Correct.
21 Correct 7 ms 2912 KB Correct.
22 Correct 12 ms 3412 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4396 KB Correct.
2 Correct 23 ms 3796 KB Correct.
3 Incorrect 485 ms 62336 KB Wrong Answer.
4 Halted 0 ms 0 KB -