oj.uz

Submission #983213

# Submission time Handle Problem Language Result Execution time Memory
983213 2024-05-15T09:30:05 Z vjudge1 Cyberland (APIO23_cyberland) C++17
0 / 100
 1979 ms 59820 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double

const ll NMAX = 1e5 + 5;
vector<pair<ll,ll> > g[NMAX];
vector<vector<double> > dis(NMAX, vector<double>(31) );

double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	for(long long i = 1; i <= n; i++){
		g[i].clear();
		for(long long j = 0; j <= 30; j++) dis[i][j] = 1e18;
	}
	h++;
    for(long long i = 0; i < m; i++){
		g[x[i] + 1].push_back({y[i] + 1, c[i]});
		g[y[i] + 1].push_back({x[i] + 1, c[i]});
	}
	priority_queue<tuple<double,long long,long long>, vector<tuple<double,long long,long long> >, greater<tuple<double,long long,long long> > > q;
	q.push({0, 1, 0});
	dis[1][0] = 0;
	while(!q.empty()){
		auto [dist, v, u] = q.top();
		q.pop();
		
		if(dist > dis[v][u]) continue;
		
		for(auto [to, cost] : g[v]){
			if(arr[to - 1] == 2 and u < 30 and (dist + cost) / 2 < dis[to][u + 1]){
				dis[to][u + 1] = ((double)dist + cost) / 2.0;
				q.push({dis[to][u + 1], to, u + 1});
			}
			if(arr[to - 1] == 0 and dis[to][u] > 0){
				dis[to][u] = 0;
				q.push({dis[to][u], to, u});
			}
			if(dist + cost < dis[to][u]){
				dis[to][u] = dist + cost;
				q.push({dis[to][u], to, u});
			}
		}
	}
	double ans = 1e18;
	for(long long i = 0; i <= k; i++) ans = min(ans, dis[h][i]);
	return ans;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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