oj.uz

Submission #984734

# Submission time Handle Problem Language Result Execution time Memory
984734 2024-05-17T03:54:16 Z Jawad_Akbar_JJ Cyberland (APIO23_cyberland) C++17
0 / 100
 3000 ms 10584 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#define ll long long
const int N = (1<<18) + 1;
ll Mn[N];
vector<pair<int,int>> nei[N];

void dijkstra(int s,int n){
	for (int i=1;i<=n;i++)
		if (i != s)
			Mn[i] = 1e17;

	set<pair<ll,int>> S;
	S.insert({0,s});

	while (S.size() > 0){
		int u = (*begin(S)).second;
		for (auto [i,w] : nei[u])
			if (Mn[i] > Mn[u] + w){
				S.erase({Mn[i],i});
				Mn[i] = Mn[u] + w;
				S.insert({Mn[i],i}); 
			}
	}
}

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 (int i=0;i<m;i++){
		nei[x[i] + 1].push_back({y[i] + 1,c[i]});
		nei[y[i] + 1].push_back({x[i] + 1,c[i]});
	}
	arr[0] = 0;

	dijkstra(h,n);

	for (int i=1;i<=n;i++)
		nei[i].clear();

	double ans = -1;

	for (int i=0;i<n;i++)
		if (arr[i] == 0 and (ans == -1 or Mn[i+1] < ans))
			ans = Mn[i+1];
	return ans;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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