oj.uz

Submission #878664

# Submission time Handle Problem Language Result Execution time Memory
878664 2023-11-25T03:59:38 Z hello_there_123 Cyberland (APIO23_cyberland) C++17
15 / 100
 3000 ms 2018408 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#include "cyberland.h"

double solve(int N, int M, int K, int end, std::vector<int> x, std::vector<int> y, std::vector<int> z, std::vector<int> arr) {
 	vector<pair<int,int> >v[N+3];  //node, val 
	for(int i=0;i<M;i++){
		v[x[i]].push_back(make_pair(y[i],z[i]));
		v[y[i]].push_back(make_pair(x[i],z[i]));
	}
	priority_queue<pair<double, pair<int,int> >, vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > pq;
	//val, node, k
	double dist[N+3][K+3];
	bool vis[N+3];
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(0);
	vis[0] = 1;
	while(!q.empty()){
		int no = q.front();
		q.pop();
		for(auto p:v[no]){
			if(!vis[p.first])q.push(p.first);
			vis[p.first] = 1;
		}
	}
	for(int i=0;i<N;i++){
		if(vis[i] == 1 && (arr[i] == 0 || i==0)){
			for(int j=0;j<=K;j++){
				dist[i][j] = 0;
				pq.push(mp(0,mp(i,j)));
			}
		}
		else for(int j=0;j<=K;j++) dist[i][j] = -1;
	}
	while(!pq.empty()){
		double val = pq.top().first;
		int no = pq.top().second.first;
		int k = pq.top().second.second;
		pq.pop();
		if(no == end) continue;
		for(auto p: v[no]){
			if(dist[p.first][k] == -1 || dist[p.first][k] > val + (double) p.second){
				
				dist[p.first][k] = val+(double)p.second;
				pq.push(mp(val+(double)p.second,mp(p.first,k)));
			}/*
			if(k == K || arr[p.first]!=2) continue;
			if(dist[p.first][k+1] == -1 || dist[p.first][k+1] > (val+(double)p.second)/2){
				dist[p.first][k+1] = (val+(double)p.second)/2;
				pq.push(mp((val+(double)p.second)/2, mp(p.first,k+1)));
			}*/
		}
	}
	double ans = 1e15;
	for(int i=0;i<=K;i++){
		if(dist[end][i]!=-1) ans = min(ans, dist[end][i]);
	}
	if(vis[end] == 0) return -1;
	assert(ans!=1e15);
	 return ans;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1812 KB Correct.
2 Correct 220 ms 1940 KB Correct.
3 Correct 211 ms 1972 KB Correct.
4 Correct 227 ms 2088 KB Correct.
5 Correct 217 ms 2084 KB Correct.
6 Correct 198 ms 6164 KB Correct.
7 Correct 267 ms 6096 KB Correct.
8 Correct 109 ms 9932 KB Correct.
9 Correct 180 ms 1420 KB Correct.
10 Correct 171 ms 1364 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1900 KB Correct.
2 Correct 124 ms 2136 KB Correct.
3 Correct 136 ms 1936 KB Correct.
4 Correct 131 ms 6380 KB Correct.
5 Correct 96 ms 1296 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3204 ms 2018408 KB Time limit exceeded
2 Halted 0 ms 0 KB -