oj.uz

Submission #841013

# Submission time Handle Problem Language Result Execution time Memory
841013 2023-09-01T04:48:13 Z GoldLight Cyberland (APIO23_cyberland) C++17
97 / 100
 638 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);
	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, 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2772 KB Correct.
2 Correct 18 ms 2884 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3028 KB Correct.
2 Correct 22 ms 3048 KB Correct.
3 Correct 21 ms 3056 KB Correct.
4 Correct 25 ms 3040 KB Correct.
5 Correct 22 ms 3056 KB Correct.
6 Correct 20 ms 6040 KB Correct.
7 Correct 29 ms 6028 KB Correct.
8 Correct 14 ms 9464 KB Correct.
9 Correct 21 ms 2756 KB Correct.
10 Correct 20 ms 2756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3032 KB Correct.
2 Correct 20 ms 3008 KB Correct.
3 Correct 21 ms 3156 KB Correct.
4 Correct 21 ms 2772 KB Correct.
5 Correct 21 ms 2644 KB Correct.
6 Correct 6 ms 5596 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22484 KB Correct.
2 Correct 22 ms 3028 KB Correct.
3 Correct 22 ms 3076 KB Correct.
4 Correct 22 ms 3020 KB Correct.
5 Correct 40 ms 2752 KB Correct.

Subtask #5
7.0 / 7.0

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

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3140 KB Correct.
2 Correct 18 ms 3060 KB Correct.
3 Correct 45 ms 28460 KB Correct.
4 Correct 16 ms 4956 KB Correct.
5 Correct 20 ms 2788 KB Correct.
6 Correct 22 ms 3112 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3156 KB Correct.
2 Correct 13 ms 3156 KB Correct.
3 Correct 578 ms 26352 KB Correct.
4 Correct 201 ms 8920 KB Correct.
5 Correct 281 ms 17740 KB Correct.
6 Correct 133 ms 9688 KB Correct.
7 Correct 245 ms 8528 KB Correct.
8 Correct 114 ms 3812 KB Correct.
9 Correct 55 ms 3192 KB Correct.
10 Correct 53 ms 3160 KB Correct.
11 Correct 87 ms 3128 KB Correct.
12 Correct 59 ms 3200 KB Correct.
13 Correct 62 ms 3148 KB Correct.
14 Correct 251 ms 9972 KB Correct.
15 Correct 221 ms 4928 KB Correct.
16 Correct 61 ms 3116 KB Correct.
17 Correct 72 ms 3112 KB Correct.
18 Correct 57 ms 3084 KB Correct.
19 Correct 85 ms 3040 KB Correct.
20 Correct 7 ms 2644 KB Correct.
21 Correct 7 ms 2988 KB Correct.
22 Correct 11 ms 3468 KB Correct.

Subtask #8
0.0 / 3.0

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