Submission #984740

#	Time	Username	Problem	Language	Result	Execution time	Memory
984740		Jawad_Akbar_JJ	Cyberland (APIO23_cyberland)	C++17	0 / 100	28 ms	11612 KiB

cyberland

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

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

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

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

	while (S.size() > 0){
		ll u = (*begin(S)).second;
		S.erase(begin(S));
		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 (ll 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+1,n);

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

	ll ans = 1;

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3