oj.uz

Submission #841009

# Submission time Handle Problem Language Result Execution time Memory
841009 2023-09-01T04:37:28 Z GoldLight Cyberland (APIO23_cyberland) C++17
15 / 100
 641 ms 2097152 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]});
	}
	set<int> t;
	vector<bool> vis(n);
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int u=q.front(); q.pop();
		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, min(k, dis+(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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3028 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3156 KB Correct.
2 Correct 25 ms 3288 KB Correct.
3 Correct 23 ms 3264 KB Correct.
4 Correct 24 ms 3236 KB Correct.
5 Correct 26 ms 3256 KB Correct.
6 Correct 22 ms 6212 KB Correct.
7 Correct 28 ms 6184 KB Correct.
8 Correct 14 ms 9556 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 27 ms 2772 KB Correct.

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3284 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 23548 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3308 KB Correct.
2 Correct 23 ms 3336 KB Correct.
3 Correct 23 ms 3360 KB Correct.
4 Correct 23 ms 5972 KB Correct.
5 Correct 23 ms 3028 KB Correct.

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3300 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 3328 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 641 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -